Category Archives: Programming

Xcode findings

As I start experimenting with Xcode I realise that it is a tricky beast.

Xcode 10.2.1

I realised Xcode 10.2.1 used 100%+ CPU. I fixed that by reinstalling it completely.

Reainstalling Xcode I had managed to mess upp the simulators.
Error: Unable to boot device because it cannot be located on disk
Solution: Run in Terminal: xcrun simctl erase all

Xcode 7.3.1

Xcode 7.3.1 Fails to start on macOS 10.14.5.

A first iOS app with Xcode 10.2.1

Ten years too late I decided to look into iOS development. It is too late, because the Klondyke era of becoming a millionaire on simple apps is probably over. On the other hand Swift has arrived and reached version 5 so it should be a good time to get started.

What I have is

  • Mac OS 10.14.5
  • Xcode 10.2.1
  • iPhone 6s, iOS 12.2 to deploy to
  • iPad 3, iOS 9.3.5 (obsolete by Apple standard)
  • 20 years of programming experience
  • Very limited experience with Swift 5
  • No experience with Xcode, Objective-C or macOS development

I am mostly a backend-programmer, who have to do HTML/CSS/JavaScript as well. Xcode is creepy. I have thought about a few appoaches

  1. Buying a book (but a challenge to find a book with relevant complexity, mix of tutorial/reference, for Xcode 10 / Swift 5)
  2. Apples obsolete tutorial (but I was put off by the fact that it is written for Swift 3)
  3. Just playing around with Xcode (just kidding – that is too scary)
  4. Some online course, like Udemy (but it is not my way)
  5. A simple trumpet tutorial

I went for (5). It was good, because in a few hours it took me all the way from starting Xcode to running something on my iPhone.

Building for the simulator and running works. And I managed to deploy to my iPhone (it is actually quite self explanatory: connect the iPhone, select it as destination in Xcode, and later in the iPhone under settings -> general -> device management you allow the app to run).

The short version is that it all went well! But…

Obsolete iPad 3

I failed to build for my obsolete iPad 3. What happens is that all is fine, and then I come to this screen:

I type my password, and immediately it (building/signing) “Failed with exit code 1”. I can imagine two options right away

  1. I need a real developer license (not Personal Team) to do this
  2. I need an older version of Xcode to build for 9.3
    (and in that case I might need to use older project format, and perhaps not even Swift 5, I don’t know)
  3. I got some indication that with a Personal (free) developer license I can only deploy to a single test device, that would perhaps not include old devices

It actually only builds for Deployment target 12.2, no older versions in the list.

Update: Page 60 of the free Apple Book “App Development With Swift” tells clearly that a free account only supports a single device. So it is clearly a waste of time to ignore that restriction and try to deploy to my iPad.

Xcode

I have spent a few hours with this now. I wrote 4 lines of code. I have ctrl-clicked on things, dragged-and-dropped-things, added properties to things, added resources, opened panels and used shortcuts. If you are used to things like Visual Studio it will probably feel somewhat familiar. But for me, who mostly use Vim, it is very scary.

Update: Xcode turned out to use 100%+ CPU constantly. I completely removed it and reinstalled it, and it seemed to help.

Computer Requirements / Performance

I did these experiments on a MacBook Pro 6,2 (that officially does not support macOS 10.14). It has an SSD drive and 8GB or RAM. Building takes almost 10 seconds, but starting the simulator and loading the app takes almost a minute. The computer clearly gets warm. Neither Xcode nor the simulator consumes much memory (Activity Monitory says about 200Mb each). Obviously, if you run the simulator much in your daily work, a faster CPU is worth it.

I think my 1440×900 display may be the biggest problem if I want to do anything real thought.

Conclusion

I have mixed feelings, it could be worse and better. I clearly need to find a way to be quickly guided through building different types of apps. I think I need a few days being guided through Xcode until both Xcode and the different project artifacts feel somewhat natural.

I have a simple app I want to build for myself, but right now it feels much to intimidating.

I found that Apple has released a free online book (available in their Books application) called App Development with Swift. That seems to be a good option.

Simple Mobile First Design

If you build a web site today you need to think about the experience on mobiles, tablets and desktops with different screen sizes. This is not very easy. In this article I have applications (SPAs) in mind rather than sites/pages.

If you are a real, ambitious, skilled designer with a significant budget, there is nothing stopping you from doing it right. Responsive design is dead, because most often you have no choice, so it is just design.

However, you may not have that budget, skill, time and ambition, but you still need to think about vastly different screen sizes. Or perhaps you just need to build a simple native-app-like website.

Two separate implementations

In many cases I would argue that it makes sense to simply make a separate site for mobile and desktop. There are many arguments but I will give one: use cases are often very different. A desktop app is often opened, kept open for a long time, and much data may be presented and analysed on screen, in memory. A mobile app is often opened shortly, to accomplish a single task, and then closed. This means that you probably want to manage state, data and workflow very differently as well.

Bootstrap (or similar)

There are frameworks (like Bootstrap) and technologies like Flexbox to allow you to build a responsive app. Before using those, I think you should ask yourself a question.

How do you want to take advantage of more screen space?

Think of regular desktop applications (Word, Photoshop, Visual Studio) or your operating system: when you have more screen available you can have more stuff next to each other. You can have more windows and more panels at the same time. Mostly. Also, but less so, small things get larger (when they benefit from it). It helps to be able to see an entire A4 page when you work with Word. But when you have an Excel sheet with 4 used columns, those don’t use your entire screen just because they can.

Bootstrap tends to create larger space between elements, and larger elements where it is not needed (dropdown <select>, input fields). I say tends to, because if you are good and very careful, you can probably do a better job than I can. But it is not automatic and it is not trivial, to make it good

What I mean is that if my calendar/table looks gorgeous when it is 400px wide, what good does it make to make it larger if the screen gets larger? So I think a better approach to responsiveness is to say that my calendar/table takes 400px. If I have more space available, I can show something else as well.

Mobile Screen Sizes

To complicate things further, mobile phones have different screen sizes, different screen resolutions, and then there are hi-resolution screens that have different virtual and physical resolutions.

So you have your table that looks good on a “standard” mobile with 320px width. What do you want to do if the user has a better/larger screen?

  1. make it look exactly the same (just better/larger)?
  2. reactively change the way your app looks and works?

If you are opting for (2), I need to wonder why, really?

I argue that if you pick (1) you can make development, testing, documentation and support easier. And your users will have a more consistent experience. At the expense that those with a large mobile may not get the most out of it when using your app.

I propose a simple Mobile First Responsive design

What I propose is not for everyone and everywhere. It may suck for your product and project. That is fine, there are different needs.

I propose a Mobile First (Semi-)Responsive design:

  1. Pick a width (320px is fine).
  2. Design all parts, all pages, all controllers of your app for that width.
  3. On mobile, set the viewport to your width for consistent behaviour on all mobiles.
  4. Optionally, on desktop (and possibly tablets), allow pages to open next to each other rather than on top of (and hiding) each other to make some use of more screen when available.

Seems crazy? Please check out my Proof of Concept and decide for yourself! It is only a PoC. It is not a framework, not a working app, not demonstrating Vue best practices, and it is not very pretty. Under Settings (click ?) you can check/change between Desktop, Tablet and Mobile mode (there is a crude auto-discover mechanism in place but it is not perfect). You can obviously try it with “Responsive Design Mode” in your browser and that should work quite fine (except some elements don’t render correctly).

Implementation Details

First, I set (despite this is not normally a recommended thing to do):

<meta id="viewport" name="viewport" content="width=320">

Later I use JavaScript to change this to 640 on a tablet, to allow two columns. Desktops should ignore it.

Second, I use a header div fixed at the top, a footer div fixed at the bottom, and the rest of the page has corresponding margins (top/bottom).

.app_headers {
   position: fixed;
   top: 0;
   left: 0;
 }
 .app_header {
   float: left;
   height: 30px;
   width: 320px;
 }
 .app_footers {
   position: fixed;
   bottom: 0;
   left: 0;
 }
 .app_footer {
   float: left;
   height: 14px;
   width: 320px;
 }
 .app_pages {
   clear: both;
 }
 .app_page {
   margin-top: 30px;
   margin-bottom: 12px;
   width: 320px;
   float: left;
 }

In mobile mode I just add one app_header, app_footer and app_page (div with class). But for Tablets and Desktops I can add more of them (equally many) as the user navigates deeper into the app. It is basically:

<div class="app_headers">
  <div class="app_header">
    Content of first header (to the left)
  </div>
  <div class="app_header">
    Content of second header (to the right)
  </div>
</div>
<div class="app_pages">
  <div class="app_page">
    Content of first page (to the left)
  </div>
  <div class="app_page">
    Content of second page (to the right)
  </div>
</div>
<div class="app_footers">
  <div class="app_footer">
    Content of first footer (to the left)
  </div>
  <div class="app_footer">
    Content of second footer (to the right)
  </div>
</div>

I use little JavaScript to not add too many pages side-by-side should the display/window not be large enough.

It is a good idea to reset margins, paddings and borders to 0 on common items.

I also found that you need a font size of 16px on iPhone, otherwise the Apple mobile Safari browser will immediately zoom when user edits <input> and <select>.

Most effort when I wrote my Proof of Concept was

  1. Getting the HTML/CSS right and as simple as possible (I am simply not good enough with HTML/CSS to just get it right)
  2. Implementing a “router” that supports this behaviour

Being able to scroll the different pages separately would be possible, a bit more complicated, and perhaps not so desirable.

Conclusions

Exploiting the viewport you can build a web app that works fine on different mobiles, and where the issue with different screen sizes and screen resolution is quite much out of your way.

The site will truly be mobile-first, but with the side-by-side-strategy presented, your users can take advantage of larger screens on non-mobiles as well.

This way, you can build a responsive app, with quite little need for testing on different devices as the app grows. You just need to keep 320px in mind, and have a clear idea about navigating your site.

First look at Swift

Apple invented the Swift programming language to make application programming for iOS and macOS a better experience. If you are new to all this (as I am), I guess there are three approaches (depending on your background):

  1. Learn with the Swift Playground App for iOS
  2. Find a book/guide/tutorial to build actual iOS apps (learning Swift along the way)
  3. Use tools that you are used to, solving problems you are familiar with, using Swift (a programmers’ approach)

I decided to just write some Swift code. There is a cool web page called Rosettacode.org with implementations of different “problems” in different languages. I started looking at Swift code there to see if I could learn anything, and decided I could to better. (Admittedly, that is quite arrogant: I have never written a line of Swift code before, and now contribute Swift code)

I started looking at the problem Caesar Encryption and solved it for Swift. The full code comes below (in case someone changes it on Rosettacode)

I have a C/C#/Java/JavaScript background. This is what I find most notable about Swift.

Backward declaration of variables, arguments and function return types. Type comes after the name (with colon in between).

Named parameters to function, unless you prepend an _ to the name.

Closures can be written (quite just) like in JavaScript. (see charRotateWithKey in the caesar function)

Wrapping/optional: a normal variable, after it is declared must have a valid value. The language ensures this for you. Look at the first line in the function charRotate below: the ! means that if the parameter c does not have an ascii value the program will terminate right there. Look at the line starting with guard in main. The language guarantees that key is a valid integer after the guard, otherwise the function (program) must exit. I am far from an expert on this, find a better source! But you can’t do what you do in C/C#/Java/JavaScript – just hope it goes well, and if it does not catch an exception or deal with it afterwards.

ARC rather than garbage collection or explicit memory management. This matters not in my program, but it is worth mentioning. I first thought Swift and Rust were very similar and that it is more or less an incident that they are different languages, but I don’t really think so anymore.

The swift command can be used not only to compile a source file. It can be used to set up a swift project (directory), run tests, run the REPL (read-eval-print-loop) and more things. This seems quite nice, but I will write no more of it here.

My program below demonstrates type conversions, command arguments, usage of map and closures, string and ascii low level operations and output.

I think Swift is a quite fine language that I would be happy to use. I notice that the language has evolved quite much over the few years it has exited. So when you find things on the web or stackoverflow, you might not find current best practices.

func usage(_ e:String) {
   print("error: \(e)")
   print("./caeser -e 19 a-secret-string")
   print("./caeser -d 19 tskxvjxlskljafz")
 }
  
 func charIsValid(_ c:Character) -> Bool {
   return c.isASCII && ( c.isLowercase || 45 == c.asciiValue ) // '-' = 45
 }
  
 func charRotate(_ c:Character, _ by:Int) -> Character {
   var cv:UInt8! = c.asciiValue
   if 45 == cv { cv = 96 }  // if '-', set it to 'a'-1
   cv += UInt8(by)
   if 122 < cv { cv -= 27 } // if larget than 'z', reduce by 27
   if 96 == cv { cv = 45 }  // restore '-'
   return Character(UnicodeScalar(cv))
 }
  
 func caesar(_ enc:Bool, _ key:Int, _ word:String) -> String {
   let r = enc ? key : 27 - key
   func charRotateWithKey(_ c:Character) -> Character {
     return charRotate(c,r)
   }
   return String(word.map(charRotateWithKey))
 }
  
 func main() {
   var encrypt = true
  
   if 4 != CommandLine.arguments.count {
     return usage("caesar expects exactly three arguments")
   }
  
   switch ( CommandLine.arguments[1] ) {
   case "-e":
     encrypt = true
   case "-d":
     encrypt = false
   default:
     return usage("first argument must be -e (encrypt) or -d (decrypt)")
   }
  
   guard let key = Int(CommandLine.arguments[2]) else {
     return usage("second argument not a number (must be in range 0-26)")
   }
  
   if key < 0 || 26 < key {
     return usage("second argument not in range 0-26")
   }
  
   if !CommandLine.arguments[3].allSatisfy(charIsValid) {
     return usage("third argument must only be lowercase ascii characters, or -")
   }
  
   let ans = caesar(encrypt,key,CommandLine.arguments[3])
   print("\(ans)")
 }
  
 func test() {
   if ( Character("a") != charRotate(Character("a"),0) ) {
     print("Test Fail 1")
   }
   if ( Character("-") != charRotate(Character("-"),0) ) {
     print("Test Fail 2")
   }
   if ( Character("-") != charRotate(Character("z"),1) ) {
     print("Test Fail 3")
   }
   if ( Character("z") != charRotate(Character("-"),26)) {
     print("Test Fail 4")
   }
   if ( "ihgmkzma" != caesar(true,8,"a-zecret") ) {
     print("Test Fail 5")
   }
   if ( "a-zecret" != caesar(false,8,"ihgmkzma") ) {
     print("Test Fail 6")
   }
 }
  
 test()
 main()

Performance, Node.js & Sorting

I will present two findings that I find strange in this post:

  1. The performance of Node.js (V8?) has clearly gotten consistently worse with newer Node.js versions.
  2. The standard library sort (Array.prototype.sort()) is surprisingly slow, often slower than a simple textbook mergesort.

My findings in this article are based on running a simple program mergesort.js on different computers and different node versions.

You may also want to read this article about sorting in Node.js. It applies to V8 version 7.0, which should be used in Node.js V11.

The sorting algorithms

There are three sorting algorithms compared.

  1. Array.prototype.sort()
  2. mergesort(), a textbook mergesort
  3. mergesort_opt(), a mergesort that I put some effort into making faster

Note that mergesort is considered stable and not as fast as quicksort. As far as I understand from the above article, Node.js used to use quicksort (up to V10), and from V11 uses something better called Timsort.

My mergesort implementations (2) (3) are plain standard JavaScript. Nothing fancy whatsoever (I will post benchmarks using Node.js v0.12 below).

The data to be sorted

There are three types of data to be sorted.

  1. Numbers (Math.random()), compared with a-b;
  2. Strings (random numbers converted to strings), compared with default compare function for sort(), and for my mergesort simple a<b, a>b compares to give -1, 1 or 0
  3. Objects, containing two random numbers a=[0-9], b=[0-999999], compared with (a.a-b.a) || (a.b-b.b). In one in 10 the value of b will matter, otherwise looking at the value of a will be enough.

Unless otherwise written the sorted set is 100 000 elements.

On Benchmarks

Well, just a standard benchmark disclaimer: I do my best to measure and report objectively. There may be other platforms, CPUs, configurations, use cases, datatypes, or array sizes that give different results. The code is available for you to run.

I have run all tests several times and reported the best value. If anything, that should benefit the standard library (quick)sort, which can suffer from bad luck.

Comparing algorithms

Lets start with the algorithms. This is Node V10 on different machines.

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
sort() merge m-opt sort() merge m-opt sort() merge m-opt
NUC i7 82 82 61 110 81 54 95 66 50
NUC i5 113 105 100 191 130 89 149 97 72
NUC Clrn 296 209 190 335 250 196 287 189 157
RPi v3 1886 1463 1205 2218 1711 1096 1802 1370 903
RPi v2 968 1330 1073 1781 1379 904 1218 1154 703

The RPi-v2-sort()-Numbers stand out. Its not a typo. But apart from that I think the pattern is quite clear: regardless of datatype and on different processors the standard sort() simply cannot match a textbook mergesort implemented in JavaScript.

Comparing Node Versions

Lets compare different node versions. This is on a NUC with Intel i5 CPU (4th gen), running 64bit version of Ubuntu.

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
sort() merge m-opt sort() merge m-opt sort() merge m-opt
v11.13.0 84 107 96 143 117 90 140 97 71
v10.15.3 109 106 99 181 132 89 147 97 71
v8.9.1 85 103 96 160 133 86 122 99 70
v6.12.0 68 76 88 126 92 82 68 83 63
v4.8.6 51 66 89 133 93 83 45 77 62
v0.12.9 58 65 78 114 92 87 55 71 60

Not only is sort() getting slower, also running “any” JavaScript is slower. I have noticed this before. Can someone explain why this makes sense?

Comparing different array sizes

With the same NUC, Node V10, I try a few different array sizes:

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
sort() merge m-opt sort() merge m-opt sort() merge m-opt
10 000 10 9 11 8 12 6 4 7 4
15 000 8 15 7 13 14 11 6 22 7
25 000 15 35 12 40 27 15 11 25 18
50 000 35 56 34 66 57 37 51 52 30
100 000 115 107 97 192 138 88 164 101 72
500 000 601 714 658 1015 712 670 698 589 558

Admittedly, the smaller arrays show less difference, but it is also hard to measure small values with precision. So this is from the RPi v3 and smaller arrays:

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
sort() merge m-opt sort() merge m-opt sort() merge m-opt
5 000 34 57 30 46 59 33 29 52 26
10 000 75 129 64 100 130 74 63 104 58
20 000 162 318 151 401 290 166 142 241 132
40 000 378 579 337 863 623 391 344 538 316

I think again quite consistently this looks remarkably bad for standard library sort.

Testing throughput (Version 2)

I decided to measure throughput rather than time to sort (mergesort2.js). I thought perhaps the figures above are misleading when it comes to the cost of garbage collecting. So the new question is, how many shorter arrays (n=5000) can be sorted in 10s?

(count)  ===== Numbers =====   ===== Strings =====   ==== Objects =====
sort() merge m-opt sort() merge m-opt sort() merge m-opt
v11.13.0 3192 2538 4744 1996 1473 2167 3791 2566 4822
v10.15.3 4733 2225 4835 1914 1524 2235 4911 2571 4811
RPi v3 282 176 300 144 126 187 309 186 330

What do we make of this? Well the collapse in performance for the new V8 Torque implementation in Node v11 is remarkable. Otherwise I notice that for Objects and Node v10, my optimized algorithm has no advantage.

I think my algorithms are heavier on the garbage collector (than standard library sort()), and this is why the perform relatively worse for 10s in a row.

If it is so, I’d still prefer to pay that price. When my code waits for sort() to finish there is a user waiting for a GUI update, or for an API reply. I rather see a faster sort, and when the update/reply is complete there is usually plenty of idle time when the garbage collector can run.

Optimizing Mergesort?

I had some ideas for optimizing mergesort that I tried out.

Special handling of short arrays: clearly if you want to sort 2 elements, the entire mergesort function is heavier than a simple function that sorts two elements. The article about V8 sort indicated that they use insertion sort for arrays up to length 10 (I find this very strange). So I implemented special functions for 2-3 elements. This gave nothing. Same performance as calling the entire mergesort.

Less stress on the garbage collector: since my mergesort creates memory nodes that are discarded when sorting is complete, I thought I could keep those nodes for the next sort, to ease the load on the garbage collector. Very bad idea, performance dropped significantly.

Performance of cmp-function vs sort

The relevant sort functions are all K (n log n) with different K. It is the K that I am measuring and discussing here. The differences are, after all, quite marginal. There is clearly another constant cost: the cost of the compare function. That seems to matter more than anything else. And in all cases above “string” is just a single string of 10 characters. If you have a more expensive compare function, the significance of sort() will be even less.

Nevertheless, V8 is a single threaded environment and ultimately cycles wasted in sort() will result in overall worse performance. Milliseconds count.

Conclusions

Array.prototype.sort() is a critical component of the standard library. In many applications sorting may be the most expensive thing that takes place. I find it strange that it does not perform better than a simple mergesort implementation. I do not suggest you use my code, or start looking for better sort() implementations out there right away. But I think this is something for JavaScript programmers to keep in mind. However, the compare function probably matters more in most cases.

I find it strange that Node v11, with Timsort and V8 Torque is not more of an improvement (admittedly, I didnt test that one very much).

And finally I find it strange that Node.js performance seems to deteriorate with every major release.

Am I doing anything seriously wrong?

JavaScript Double Linked List

JavaScript has two very powerful and flexible build in data structures: [] and {}. You can program rather advanced JavaScript for years without needing anything else.

Nevertheless I had a conversation about possible advantages of using a linked list (instead of an array). Linked lists are not very popular, Stroustrup himself has suggested they should be avoided. But what if you mostly do push(), pop(), shift() and unshift() and never access an item by its index? Higher order functions as map(), reduce(), filter() and sort(), as well as iterators should be just fine.

I decided to implement a Double Linked List in JavaScript making it (mostly) compatible with Array and do some tests on it. The code both of the DoubleLinkedList itself, and the unit tests/benchmarks are available.

Disclaimer

This is a purely theoretical, academical and nerdy experiment. The DoubleLinkedList offers no advantages over the built in Array, except for possible performance advantages in edge cases. The disadvantages compared to Array are:

  • Lower performance in some cases
  • Less features / limited API
  • Less tested and proven
  • An extra dependency, possible longer application loading time

So, my official recommendation is that you read this post and perhaps look at the code for learning purposes. But I really doubt you will use my code in production (although you are welcome to).

Benchmarks

Benchmarks are tricky. In this case there are three kinds of benchmarks:

  1. Benchmarks using array[i] to get the item at an index. This is horrible for the linked list. I wrote no such benchmarks.
  2. Benchmarks testing map(), reduce(), filter(), that I wrote but that show consistently no relevant and interesting differences between built in Array and my DoubleLinkedList (my code is essentially equally fast as the standard library array code, which on one hand is impressive, and on the other hand is reason not to use it).
  3. Benchmarks where my DoubleLinkedList does fine, mostly that heavily depends on push(), pop(), shift() and unshift().

The only thing I present below is (3). I have nothing for (1), and (2) shows nothing interesting.

The machines are in order an Hades Canyon i7-NUC, an old i5-NUC, a newer Celeron-NUC, an Acer Chromebook R13 (with an ARMv8 CPU), A Raspberry Pi v3, and a Raspberry Pi V2. The Chromebook runs ChromeOS, the i7 runs Windows, the rest run Linux.

My benchmarks use Math.random() to create test data. That was not very smart of me because the variation between test runs is significant. The below numbers (milliseconds) are the median value of running each test 41 times. You can see for yourself that the values are quite consistent.

The tested algorithms

The push(), pop(), shift(), unshift() tests use the array/list as a queue and push 250k “messages” throught it, keeping the queue roughly 10k messages.

The mergesort() test is a mergesort built on top of the datastructures using push()/shift().

The sort() test is the standard Array.sort(), versus a mergesort implementation for DoubleLinkedList (it has less overhead than mergesort(), since it does not create new objects for every push()).

Benchmark result

                    Node8   ============== Node 10 =====================
(ms) NUCi7 NUCi7 NUCi5 NUC-C R13 RPiV3 RPiV2
unshift/pop 250k
Array 679 649 1420 1890 5216 11121 8582
D.L.L. 8 13 10 20 40 128 165
push/shift 250k
Array 37 31 31 49 143 388 317
D.L.L. 10 12 10 19 44 115 179
mergesort 50k
Array 247 190 300 466 1122 3509 3509
D.L.L. 81 88 121 244 526 1195 1054
sort 50k
Array 53 55 59 143 416 1093 916
D.L.L. 35 32 42 84 209 543 463

What do we make of this?

  • For array, push/shift is clearly faster than unshift/pop!
  • It is possible to implement a faster sort() than Array.sort() of the standard library. However, this may have little to do with my linked list (I may get an even better result if I base my implementation on Array).
  • I have seen this before with other Node.js code but not published it: the RPiV2 (ARMv7 @900MHz) is faster than the RPiV3 (ARMv8 @1200Mhz).
  • I would have expected my 8th generation i7 NUC (NUC8i7HVK) to outperform my older 4th generation i5 NUC (D54250WYK), but not so much difference.

More performance findings

One thing I thought could give good performance was a case like this:

x2 = x1.map(...).filter(...).reduce(...)

where every function creates a new Array just to be destroyed very soon. I implemented mapMutate and filterMutate for my DoubleLinkedList, that reuse existing List-nodes. However, this gave very little. The cost of the temporary Arrays above seems to be practically insignificant.

However for my Double linked list:

dll_1 = DoubleLinkedList.from( some 10000 elements )
dll_1.sort()
dll_2 = DoubleLinkedList.from( some 10000 elements )

Now
dll_1.map(...).filter(...).reduce(...) // slower
dll_2.map(...).filter(...).reduce(...) // faster

So it seems I thought reusing the list-nodes would be a cost saver, but it turns out to produce cache-misses instead

Using the Library

If you feel like using the code you are most welcome. The tests run with Node.js and first runs unit tests (quickly) and then benchmarks (slower). As I wrote earlier, there are some Math.random() in the tests, and on rare occations statistically unlikely events occur, making the tests fail (I will not make this mistake again).

The code itself is just for Node.js. There are no dependencies and it will require minimal work to adapt it to any browser environment of your choice.

The code starts with a long comment specifying what is implemented. Basically, you use it just as Array, with the exceptions/limitations listed. There are many limitations, but most reasonable uses should be fairly well covered.

Conclusion

It seems to make no sense to replace Array with a linked list in JavaScript (Stroustrup was right). If you are using Array as a queue be aware that push/shift is much faster than unshift/pop. It would surprise me much if push/pop is not much faster than unshift/shift for a stack.

Nevertheless, if you have a (large) queue/list/stack and all you do is push, pop, shift, unshift, map, filter, reduce and sort go ahead.

There is also a concatMutate in my DoubleLinkedList. That one is very cheap, and if you for some reason do array.concat(array1, array2, array3) very often perhaps a linked list is your choice.

It should come as no surprise, but I was suprised that sort(), mergesort in my case, was so easy to implement on a linked list.

On RPiV2 vs RPiV3

I have on several occations before written about that the 900MHz ARMv7 of RPiV2 completely outperformes the 700MHz ARMv6 of RPiV1. It is about 15 times faster, and not completely clear why the difference is so big (it is that big for JavaScript, not for C typical code).

The RPiV3 is not only 300MHz faster than the RPiV2, it is also a 64-bit ARMv8 cpu compared to the 32-bit ARMv7 cpu of RPiV2. But V3 delivers worse performance than V2.

One reason could be that the RPi does not have that much RAM, and not that fast RAM either, and that the price of 64-bit is simply not worth it. For now, I have no other idea.

References

An article about sorting in V8: https://v8.dev/blog/array-sort. Very interesting read. But I tried Node version 11 that comes with V8 version 7, and the difference was… marginal at best.

Micro service separation

Lets say we have a simple service that we can start:

$ ls
my-service my-data
$ ./my-service -d my-data -p 8080

As we interact with the service over HTTP on 8080 it stores data in the my-data folder. This may seem simplified but it is basically how any network (web, file, directory, database and so on) service works.

Micro Services

Lets say you have 4 different such services responsible for different things (like html/UI, storage, log and authentication) and they work together: well you basically have a Micro Service architecture.

All your different services can have a binary and a data folder. They can all exist in the same folder. You can start, stop and update them independently. If a service is “heavy” you can can run several instances of it. The services need to know about each other and listen to different ports, but that is just a matter of configuration and it can be automated.

Separation of micro services

While the simple approach above works (and it works surprisingly well), you may run into issues such as:

  1. you want to be sure two services can’t mess with each others data
  2. a service may be heavy and should run on separate hardware
  3. the services have common dependencies but it must be possible to update them separately (dll hell)
  4. the services may not even run on the same operating systems
  5. two services may use some resource that would cause a conflict if they shared it (say both use the same windows registry keys)
  6. different teams may be responsible for different services, and they shall neither be able to mess with each other, or blame each other

Clearly, running all services on the same computer, as the same user, in the same folder is not good enough in these scenarios. What options do we have?

Separate Hardware

Traditionally, especially in the Windows world, each service got its on computer (I refer to custom application services, clearly Windows itself comes with multiple standard services running).

In Windows, you typically install something with an install Wizard. It updates and stores stuff in different places in the system (Registry, Windows folder, Program Files and perhaps more). Multiple services may not coexist completely safely. So each get a Windows server that you backup entirely in case of disaster. This is expensive, wasteful and complicated.

Virtual Machines

VMWare was founded in 1998 and VMWare workstation was released in 1999. It changed everything, especially on Windows. Instead of having multiple computers you could have one physical computer running multiple virtual computers. Such a virtual computer “thought” it was a real computer. It needed special device drivers for the virtual hardware it ran on.

This is great. But you end up duplicating megabytes, perhaps gigabytes of system files. Installation and configuration of a computer is not trivial. Even if you automate it there are many details that need to get right. And a virtual computer may need to swap/page, and does so to what it thinks is a physical drive, but it is just a file on the host computer.

Just different users

You may run your different services in the home directories of different users. In theory that could work in Windows, but it is a quite unlikely setup.

In *NIX it would mostly work fine. You can have multiple terminals and log in as multiple users at the same time. If you are root you can easily write scripts to become any user you like, and execute whatever you want in their home directory.

Also, in *NIX most software can actually be built, installed and run in a regular user home directory. Often you just build and install as the regular user:

$ ./configure --prefix=/home/service01
$ make
$ make install

Basically, *NIX is already Micro Service-ready.

Chroot

For some purposes, running in a home directory may not be optimal. Instead, you may want to run the application in an environment where everything it needs, and nothing else, is in / (the root). There is a command called chroot that allows you to do this.

But chroot is not perfect. First it is not entirely safe (there are ways to break out of it). Second, you need to populate /bin, /lib, /etc with everything you need, and that may not be obvious. And you will only run the service in the chroot – the administrator or devops team need to access the computer normally, and they are not restricted to or don’t just see the chroot.

Containers

While all the above methods can be made to work for a microservice architecture, much effort has been made to come up with something even better, especially for deploying applications to the cloud: containers.

Containers and the tools around them focus much on development, deployment and automation. They are made for DevOps. It is cheap to configure, create, run and discard containers.

Application containers (Docker) are quite similar to a chroot, but they exist on Windows too. It is about putting everything an appliation needs, and nothing else, into the container so you can easily move, reconfigure it, duplicate it, and so on without touching your operating system itself. The issue of having exactly the right OS version, with the right patches, and the right versions of the right dependencies installed is much simplified when you can create a stable container that you can run on any machine capable of running containers.

System containers (LXC) are quite similar to a virtual machine. But while a virtual machine emulates hardware and runs a complete kernel, a system container just emulates a kernel (that may require some contemplation). It has all the advantages of a Linux virtual machine on Linux, but less of the costs.

Conclusion and Summary

Containers are popular, and for good reasons. But they are also a bit hyped. In the end of they day, you have your service code, and when you run it, it (perhaps) works on local data. That is it. You can separate, scale, isolate, secure, manage, deploy, monitor and automate this on different levels:

  1. Run your services in different folders (most light weight)
  2. Run your services as different users
  3. Run your services in chroots
  4. Create appliation containers for your services
  5. Create system containers for your services
  6. Create virtual machines for your services
  7. Get physical machines for your services (most heavy weight)

You can clearly mix and match strategies (you may very well need to).

And the price of a Raspberry Pi is so low, that even #7 can be very cheap for many purposes.

Where to ‘use strict’ with Object.freeze()?

I have coded JavaScript short enough time to consider ‘use strict’ a mandatory and obvious feature of the language to use. I always use it unless I forget to.

A while ago I was aware of Object.freeze(). I have been thinking about different ways to exploit this (strict) feature for a while and I now have a very good use case: freeze indata in unit tests to ensure my tested functions don’t incidentally change indata (pure functions are good, pure functions don’t change indata, and it is hard to really guarantee a function in JavaScript is pure).

Imagine I am writing a function that calculates the average and I have a test for it.

const averageOfArray1 = (a) => {
let s = 0;
for ( let i=0 ; i<a.length ; i++ ) s+=a[i];
return s/a.length;
};

describe('test avg', () => {
it('should give the average value of 2', () => {
const a = [1,2,3];
assert.equal(2, averageOfArray1(a) );
});
});

If averageOfArray mutates its input, it would be a serious bug, and the above test would not detect it. Lets look at a different implementation:

const averageOfArray2 = (a) => {
for ( let i=1 ; i<a.length ; i++ ) a[0] += a[i];
return a[0]/a.length;
};

describe('test avg', () => {
it('should give the average value of 2', () => {
const a = [1,2,3];
assert.equal(2, averageOfArray2(a) );
});
});

Some genious “optimized” the function by eliminating an unnecessary variable (s), and the test still passes! However, if the tests where written:

describe('test loop', () => {
it('should give the average value of 2', () => {
const a = Object.freeze([1,2,3]);
assert.equal(2, averageOfArray2(a) );
});
})

the tests would fail! Much better. How do the tests fail? This is what I get:

1) test avg
should give the average value of 2:

AssertionError [ERR_ASSERTION]: 2 == 0.3333333333333333
+ expected - actual
-2
+0.3333333333333333

So it appears that the first element [0] of the array was never changed, thus the return value of 0.3333. But no exception was thrown. If I instead would ‘use strict’ for the entire code:

 'use strict';

const assert = require('assert');

const averageOfArray2 = (a) => {
for ( let i=1 ; i<a.length ; i++ ) a[0] += a[i];
return a[0]/a.length;
};
describe('test avg', () => {
it('should give the average value of 2', () => {
const a = Object.freeze([1,2,3]);
assert.equal(2, averageOfArray2(a));
});
});

instead I get:

1) test avg
should give the average value of 2:
TypeError: Cannot assign to read only property '0' of object '[object Array]'
at averageOfArray2 (avg.js:12:45)
at Context.it (avg.js:20:25)

which is what I really wanted.

So it APPEARS to me that without ‘use strict’ the frozen object is not changed, but changing it just fails silently. With ‘use strict’ I get an exception right way, which leads me to the question where I can put use strict? This is what I found:

 // 'use strict';  // GOOD

const assert = require('assert');

// 'use strict'; // BAD

const averageOfArray2 = (a) => {
// 'use strict'; // GOOD
let i;
// 'use strict'; // BAD
for ( i=1 ; i<a.length ; i++ ) a[0] += a[i];
return a[0]/a.length;
};
describe('test avg', () => {
// 'use strict'; // BAD
it('should give the average value of 2', () => {
const a = Object.freeze([1,2,3]);
assert.equal(2, averageOfArray2(a));
});
});

That is, ‘use strict’ should be in place where the violation actually takes place. And ‘use strict’ must be placed first in whatever function it is placed, otherwise it is silently ignored! This is probably well known to everyone, but it was not to me.

Conclusion

Object.freeze() is very useful for improved unit tests. However, you should use it together with properly placed ‘use strict’ and that is in the function begin tested (not only the unit test).

And note, if you have done Object.freeze in a unit test, and someone refactors the tested function in a way that it both:

  1. Mutates the frozen object
  2. Removes or moves ‘use strict’ to an invalid place

your unit tests may still pass, even though the function is now very dangerous.

Best way to write compare-functions

The workhorse of many (JavaScript) programs is sort(). When you want to sort objects (or numbers, actually) you need to supply a compare-function. Those are nice functions because they are very testable and reusable, but sorting is also a bit expensive (perhaps the most expensive thing your program does) so you want them fast.

For the rest of this article I will assume we are sorting som Order objects based status, date and time (all strings).

The naive way to write this is:

function compareOrders1(a,b) {
if ( a.status < b.status ) return -1;
if ( a.status > b.status ) return 1;
if ( a.date < b.date ) return -1;
if ( a.date > b.date ) return 1;
if ( a.time < b.time ) return -1;
if ( a.time > b.time ) return 1;
return 0;
}

There are somethings about this that is just not appealing: too verbose, risk of a typo, and not too easy to read.

Another option follows:

function cmpStrings(a,b) {
if ( a < b ) return -1;
if ( a > b ) return 1;
return 0;
}

function compareOrders2(a,b) {
return cmpStrings(a.status,b.status)
|| cmpStrings(a.date ,b.date )
|| cmpStrings(a.time ,b.time );
}

Note that the first function (cmpStrings) is highly reusable, so this is shorter code. However, there is still som repetition, so I tried:

function cmpProps(a,b,p) {
return cmpStrings(a[p], b[p]);
}

function compareOrders3(a,b) {
return cmpProps(a,b,'status')
|| cmpProps(a,b,'date')
|| cmpProps(a,b,'time');
}

There is something nice about not repeating status, date and time, but there is something not so appealing about quoting them as strings. If you want to go more functional you can do:

function compareOrders4(a,b) {
function c(p) {
return cmpStrings(a[p],b[p]);
}
return c('status') || c('date') || c('time');
}

To my taste, that is a bit too functional and obscure. Finally, since it comes to mind and some people may suggest it, you can concatenate strings, like:

function compareOrders5(a,b) {
return cmpStrings(
a.status + a.date + a.time,
b.status + b.date + b.time
);
}

Note that in case fields “overlap” and/or have different length, this could give unexpected results.

Benchmarks

I tried the five different compare-functions on two different machines and got this kind of results (i5 N=100000, ARM N=25000), with slightly different parameters.

In these tests I used few unique values of status and date to often hit the entire compare function.

(ms)   i5    i5    ARM
#1 293 354 507
#2 314 351 594
#3 447 506 1240
#4 509 541 1448
#5 866 958 2492

This is quite easy to understand. #2 does exactly what #1 does and the function overhead is eliminated by the JIT. #3 is trickier for the JIT since a string is used to read a property. That is true also for #4, which also requires a function to be generated. #5 puts two strings on the stack needlessly when often only the first two strings are needed to compare anyway.

Conclusion & Recommendation

My conclusion is that #3 may be the best choice, despite it is slightly slower. I find #2 clearly preferable to #1, and I think #4 and #5 should be avoided.

Lambda Functions considered Harmful

Decades ago engineers wrote computer programs in ways that modern programmers scorn at. We learn that functions were long, global variables were used frequently and changed everywhere, variable naming was poor and gotos jumped across the program in ways that were impossible to understand. It was all harmful.

Elsewhere matematicians were improving on Lisp and functional programming was developed: pure, stateless, provable code focusing on what to do rather than how to do it. Functions became first class citizens and they could even be anonymous lambda functions.

Despite the apparent conflict between object oriented, functional and imperative programming there are some universally good things:

  • Functions that are not too long
  • Functions that do one thing well
  • Functions that have no side effects
  • Functions that can be tested, and that also are tested
  • Functions that can be reused, perhaps even being general
  • Functions and variables that are clearly named

So, how are we doing?

Comparing different styles
I read code and I talk to people who have different opinions about what is good and bad code. I decided to implement the same thing following different principles and discuss the different options. I particularly want to explore different ways to do functional programming.

My language of choice is JavaScript because it allows different styles, it requires quite little code to be written, and many people should be able to read it.

My artificial problem is that I have two arrays of N numbers. One number from each array can be added in NxN different ways. How many of these are prime? That is, for N=2, if I have [10,15] and [2,5] i get [12,15,17,20] of which one number (17) is prime. In all code below I decide if a number is prime in the same simple way.

Old imperative style (imperative)
The old imperative style would use variables and loops. If I had goto in JavaScript I would use goto instead of setting a variable (p) before I break out of the inner loop. This code allows for nothing to be tested nor reused, although the function itself is testable, reusable and pure (for practical purposes and correct input, just as all the other examples).

  const primecount = (a1,a2) => {
    let i, j;
    let d, n, p;
    let retval = 0;


    for ( i=0 ; i<a1.length ; i++ ) {
      for ( j=0 ; j<a2.length ; j++ ) {
        n = a1[i] + a2[j];
        p = 1;
        for ( d=2 ; d*d<=n ; d++ ) {
          if ( 0 === n % d ) {
            p = 0;
            break;
          }
        }
        retval += p;
      }
    }
    return retval;
  }

Functional style with lambda-functions (lambda)
The functional programming equivalent would look like the below code. I have focused on avoiding declaring variables (which would lead to a mutable state) and rather using the higher order function reduce to iterate over the two lists. This code also allows for no parts to be tested or reused. In a few lines of code there are three unnamed functions, none of them trivial.

  const primecount = (a1,a2) => {
    return a1.reduce((sum1,a1val) => {
      return sum1 + a2.reduce((sum2,a2val) => {
        return sum2 + ((n) => {
          for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
          return 1;
        })(a1val+a2val);
      }, 0);
    }, 0);
  };

Imperative style with separate test function (imperative_alt)
The imperative code can be improved by breaking out the prime test function. The advantage is clearly that the prime function can be modified in a more clean way, and it can be tested and reused. Also note that the usefulness of goto disappeared because return fulfills the same task.

  const is_prime = (n) => {
    for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
    return 1;
  };

  const primecount = (a1,a2) => {
    let retval = 0;
    for ( let i=0 ; i<a1.length ; i++ )
      for ( let j=0 ; j<a2.length ; j++ )
        retval += is_prime(a1[i] + a2[j]);
    return retval;
  };

  const test = () => {
    if ( 1 !== is_prime(19) ) throw new Error('is_prime(19) failed');
  };

Functional style with lambda and separate test function (lambda_alt)
In the same way, the reduce+lambda-code can be improved by breaking out the prime test function. That function, but nothing else, is now testable and reausable.

  const is_prime = (n) => {
    for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
    return 1;
  };

  const primecount = (a1,a2) => {
    return a1.reduce((sum1,a1val) => {
      return sum1 + a2.reduce((sum2,a2val) => {
        return sum2 + is_prime(a1val+a2val);
      }, 0);
    }, 0);
  };

  const test = () => {
    if ( 1 !== is_prime(19) ) throw new Error('is_prime(19) failed');
  };

I think I can do better than any of the four above examples.

Functional style with reduce and named functions (reducer)
I don’t need to feed anonymous functions to reduce: I can give it named, testable and reusable functions instead. Now a challenge with reduce is that it is not very intuitive. filter can be used with any has* or is* function that you may already have. map can be used with any x_to_y function or some get_x_from_y getter or reader function that are also often useful. sort requires a cmpAB function. But reduce? I decided to name the below functions that are used with reduce reducer_*. It works quite nice. The first one reducer_count_primes simply counts primes in a list. That is (re)useful, testable all in itself. The next function reducer_count_primes_for_offset is less likely to be generally reused (with offset=1 it considers 12+1 to be prime, but 17+1 is not), but it makes sense and it can be tested. Doing the same trick one more time with reducer_count_primes_for_offset_array and we are done. These functions may not be reused. But they can be tested and that is often a great advantage during development. You can build up your program part by part and every step is a little more potent but still completely pure and testable (I remember this from my Haskell course long ago). This is how to solve hard problems using test driven development and to have all tests in place when you are done.

  const is_prime = (n) => {
    for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
    return 1;
  };

  const reducer_count_primes = (s,n) => {
    return s + is_prime(n);
  };

  const reducer_count_primes_for_offset = (o) => {
    return (s,n) => { return reducer_count_primes(s,o+n); };
  };

  const reducer_count_primes_for_offset_array = (a) => {
    return (s,b) => { return s + a.reduce(reducer_count_primes_for_offset(b), 0); };
  };

  const primecount = (a1,a2) => {
    return a1.reduce(reducer_count_primes_for_offset_array(a2), 0);
  };

  const test = () => {
    if ( 1 !== [12,13,14].reduce(reducer_count_primes, 0) )
      throw new Error('reducer_count_primes failed');
    if ( 1 !== [9,10,11].reduce(reducer_count_primes_for_offset(3), 0) )
      throw new Error('reducer_count_primes_for_offset failed');
    if ( 2 !== [2,5].reduce(reducer_count_primes_for_offset_array([8,15]),0) )
      throw new Error('reducer_count_primes_for_offset_array failed');
  };

Using recursion (recursive)
Personally I like recursion. I think it is easier to use than reduce, and it is great for acync code. The bad thing with recursion is that your stack will eventually get full (if you dont know what I mean, try my code – available below) for recursion depths that are far from unrealistic.  My problem can be solved in the same step by step test driven way using recursion.

  const is_prime = (n) => {
    for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
    return 1;
  };

  const primes_for_offset = (a,o,i=0) => {
    if ( i === a.length )
      return 0;
    else
      return is_prime(a[i]+o) + primes_for_offset(a,o,i+1);
  }

  const primes_for_offsets = (a,oa,i=0) => {
    if ( i === oa.length )
      return 0;
    else
      return primes_for_offset(a,oa[i]) + primes_for_offsets(a,oa,i+1);
  }

  const primecount = (a1,a2) => {
    return primes_for_offsets(a1,a2);
  };

  const test = () => {
    if ( 2 !== primes_for_offset([15,16,17],2) )
      throw new Error('primes_with_offset failed');
  };

Custom Higher Order Function (custom_higher_order)
Clearly reduce is not a perfect fit for my problem since I need to nest it. What if I had a reduce-like function that produced the sum of all NxN possible pairs from two arrays, given a custom value function? Well that would be quite great and it is not particularly hard either. In my opinion this is a very functional approach (despite its implemented with for-loops). All the functions written are independently reusable in a way not seen in the other examples. The problem with higher order functions is that they are pretty abstract, so they are hard to name, and they need to be general enough to ever be reused for practical purposes. Nevertheless, if I see it right away, I can do it. But I don’t spend time inventing generic stuff instead of solving the actual problem at hand.

  const is_prime = (n) => {
    for ( let d=2 ; d*d<=n ; d++ ) if ( 0 === n % d ) return 0;
    return 1;
  };

  const combination_is_prime = (a,b) => {
    return is_prime(a+b);
  };

  const sum_of_combinations = (a1,a2,f) => {
    let retval = 0;
    for ( let i=0 ; i<a1.length ; i++ )
      for ( let j=0 ; j<a2.length ; j++ )
        retval += f(a1[i],a2[j]);
    return retval;
  };

  const primecount = (a1,a2) => {
    return sum_of_combinations(a1,a2,combination_is_prime);
  };

  const test = () => {
    if ( 1 !== is_prime(19) )
      throw new Error('is_prime(19) failed');
    if ( 0 !== combination_is_prime(5,7) )
       throw new Error('combination_is_prime(5,7) failed');
    if ( 1 !== sum_of_combinations([5,7],[7,9],(a,b)=> { return a===b; }) )
       throw new Error('sum_of_combinations failed');
  };

Lambda Functions considered harmful?
Just as there are many bad and some good applications for goto, there are both good and bad uses for lambdas.

I actually dont know if you – the reader – agrees with me that the second example (lambda) offers no real improvement to the first example (imperative). On the contrary, it is arguably a more complex thing conceptually to nest anonymous functions than to nest for loops. I may have done the lambda-example wrong, but there is much code out there, written in that style.

I think the beauty of functional programming is the testable and reusable aspects, among other things. Long, or even nested, lambda functions offer no improvement over old spaghetti code there.

All the code and performance
You can download my code and run it using any recent version of Node.js:

$ node functional-styles-1.js 1000

The argument (1000) is N, and if you double N execution time shall quadruple. I did some benchmarks and your results my vary depending on plenty of things. The below figures are just one run for N=3000, but nesting reduce clearly comes at a cost. As always, if what you do inside reduce is quite expensive the overhead is negligable. But using reduce (or any of the built in higher order functions) for the innermost and tightest loop is wasteful.

 834 ms  : imperative
874 ms  : custom_higher_order
890 ms  : recursive
896 ms  : imperative_alt
1015 ms  : reducer
1018 ms  : lambda_alt
1109 ms  : lambda

Other findings on this topic
Functional Programming Sucks