Flight-Assist Astromech

Finally, the fix for the X-wing has arrived. I have written before here and here about my thoughts on fixing the X-wing.

The Flight-Assist Astromech costs one point and lets you make a free barrel roll or boost, unless you have a target in sight and range.

I think it is a good and well balanced upgrade, with uses outside the T65 X-wing.

T65 X-wing
I think for low cost generic X-wings (Rookie Pilots at 21p) the Flight-Assist Astromech is the best upgrade (previous options were R2 and Targetting Astromech). Does it also bring the Rookie Pilot back to play? Well, I don’t compete. I think it compensates for the worst weaknesses of the X-wing in a sensible way. In the first round(s) of the game you can boost to keep up speed with T70 or other ships, and you have more options when it comes to arriving at the battle. The first round of fire it is more likely that the T65 is actually in the fight, and not behind or all enemies out of arc. In the battle you have now options to the 4-U-turn and you can re-engage quicker and more effectively.

I tried a list I call Return of the X-wing that you find here.

How about T65 aces (Luke, Wedge, Wes)? Having a high skill means your opponents fly first and you may not be allowed to use Flight-Assist. I can see situations where BB8 (however unique) would be better. No doubt Luke, Wedge and Wes are better Flight-Assist than without. The most obvious situation is a first/second round strike where a boost or barrel roll can make them just reach. I have not tried this yet.

Finally, Flight-Assist seems to be of no significant benefit to Biggs which was important.

T70 X-wing
The T70 already has boost. Targetting Astromech is great with its 3 red maneuvers while Flight-Assist is not. Also, Poe likes R5-P9 and Nien Numb likes R3-A2. I think the T70 still has many options.

Y-wing
Flight-Assist Astromech can specifically not be used with turret weapons. This makes it interesting to combine with BTL-A4 to produce a more dog-fighting capable Y-wing. I think this was a clever Y-wing upgrade!

ARC-170
I think the ARC-170 is perhaps the ship that benefits the most of Fligth-Assist. With a maneuver dial similar to the T65 and no turrets (unlike Y-wing) it can really use boost or barrel roll. But I think (after flying only once) that Flight-Assist works very well with the Auxilliary firing arc. Normally it is quite hard to make good use of the tail gun, but if you can boost or barrel roll to get your enemy behind you it is a different story. And later with a boost it is much easier to get back in the fight. I tried this with Norra in the 10th (and so far unnamed) Horton Salm squad.

E-wing
I doubt Flight Assist will bring the Generic E-wings to the tables. And when it comes to Corran Horn he can really use a regenerating Astromech (R2-D2 or R5-P9). Perhaps Etahn A’baht could use it though.

Conclusion
I think Flight-Assist is a very good upgrade (I hope it was not too good, because while I want an upgrade for my T65s I still want a balanced game). There are old Astromechs that become even less relevant now (R2-F2, R3, R5). I think Flight-Assist helps where it was mostly needed without just making T65 more like th T70.

Y-wing: Now, on top of my list, I want new unique Y-wing pilots. There are several to choose from within Star Wars Canon universe.
Z95: The headhunter needed this flight assistance just as bad as the T65 did.

Fast binary search without Division

Arrays are simple datastructures but finding elements is not fast. However, if you have a sorted array, a favourite algorithm is Binary Search.

When it comes to JavaScript there is no binary search in the standard library. Standard functions like find and indexOf simply just don’t cut it for many purposes, being O(n).

Rosetta Code has two implementations of binary search for JavaScript. However, binary search is based on division (by 2, you split the search interval in half every iteration). In programming languages with integer math division by 2 is performed by doing a single shift, so it is a cheap operation (division is generally expensive). In JavaScript integer division by two looks like:

mid = Math.floor((lo + hi) / 2);

This is just… unacceptable. Perhaps V8 recognizes the pattern and replaces it with the right thing, I don’t care, floating point math has nothing to do with binary search and this is ugly.

Perhaps I can do better? Well, I actually can!

Instead of dividing the actual interval by 2 in every iteration you can use the powers of two: 32,16,8,4,2,1 and search with them. Lets say the array is 41 elements long. Start check element 32. If its too little try with 32+8 (skip 32+16 > 41), and if it is too large try with 16. That way you essentially do a binary search without a division.

Since I don’t want to do heap allocation for every search I calculate the powers of two before declaring the function. In the code below my maximum value is 2^31, so I can mostly search arrays of size 2^32-1. If you dont like that limit you can raise 32 to whatever you like (but at 52-53 you are running into new problems, and well before that you will run out of RAM).

function powers_init(s) {
  var i;
  var r = new Array(s);
  r[0] = 1;
  for ( i=1 ; i<s ; i++ ) {
    r[i] = 2*r[i-1];
  }
  return r;
}

var powers = powers_init(32);  // [1,2,4,8,16,32,...

function binary_search_divisionless(a, value) {
  var pix = 0;
  var aval;
  var offset0 = 0;
  var offset1;

  if ( a[0] === value ) return 0;
  while ( powers[pix+1] < a.length ) pix+= 1;

  while ( 0 <= pix ) {
    offset1 = offset0 + powers[pix];
    if ( offset1 < a.length ) {
      aval = a[offset1];
      if ( value === aval ) {
        return offset1;
      } else if ( aval < value ) {
        offset0 = offset1;
      }
    }
    pix--;
  }

  return -1;
}

It is perhaps not obvious why I check for a[0] before doing anything else. The function returns from the main while loop as soon as it finds what it is looking for. So a[offset0] does not contain the value in later iterations when offset>0. However, this is not guaranteed from the beginning when offset0=0, and it is not automatically being tested in the end. So I explicitly test it first.

Benchmark
Below follows relative performance in time for different array sizes.

Array Size:                  10      100     1000    10000   100000
=======================================================================
Standard Library indexOf   1.65     2.02    11.89    94.00   790.00
Rosetta Code Recursive     1.32     1.48     1.84     1.81     2.02
Rosetta Code Imperative    1.18     1.08     1.41     1.43     1.45
Divisionless               1.00     1.00     1.00     1.00     1.00
   - unrolled              0.93     0.76     0.82     0.79     0.78

I am satisfied that my code is consistently faster than the alternatives. What surprised me was that binary search clearly wins even for short arrays (10). The little loop before the big loop can be unrolled for significant performance gain:

//while ( powers[pix+ 1] < a.length ) pix+= 1;
  if ( powers[pix+16] < a.length ) pix+=16;
  if ( powers[pix+ 8] < a.length ) pix+= 8;
  if ( powers[pix+ 4] < a.length ) pix+= 4;
  if ( powers[pix+ 2] < a.length ) pix+= 2;
  if ( powers[pix+ 1] < a.length ) pix+= 1;

This is also the reason why 32 was a particularly good array size for the powers of two. This is a kind of optimization I would normally not let into my code. However, if you make much use of binary search on the Node.js server side of an application, go ahead.

It is also worth noting that the following patch doubles the execution time of my code!

//  if ( offset1 < a.length ) {
//    aval = a[offset1];
    if ( undefined !== ( aval = a[offset1] ) ) {

General Compare Function
With little modification, the algorithm can be used with a compare function for arrays of objects other than numbers (or strings).

Division
Since my algorithm only uses powers of 2, I can do division in JavaScript without using Math.floor. It is a quite easy change to eleminate the powers-array and divide by two instead. It turns out it make very little difference on performance (to do integer / 2 instead of array lookup). However, when I added a (meaningless) Math.floor() around the division, performance dropped the same as the the iterative version from Rosetta Code. So my intuition was correct to avoid it.

I checked the Lodash binary search code (sortedIndexOf) and it uses bit shift <<< to divide by two. Admittedly, the Lodash code is slightly faster than my code.

Conclusion
You should have a well implemented and tested binary search function available in your toolbox (admittedly, use Lodash for this). This is not the right place to lose milliseconds. For very small arrays you can argue that indexOf works equally well, but the cost of using binary search is insignificant.

Upgrading OpenWRT to LEDE

A bit late, but I wanted to upgrade OpenWRT 15.05 to LEDE 17.01.4.

It worked perfectly for my WDR 4900. The OpenWRT-to-LEDE-rebranding caused no problems.

I basically followed my own upgrade instuctions.
I also took advantage of adding files and folders to /etc/sysupgrade.conf. Those where automatically kept during the upgrade, which is nice.

Conclusion (based on one successful upgrade): if you are an old OpenWRT fan there is no reason to fear LEDE and wait for a new OpenWRT release before upgrading.

Syncthing v0.14.40, Raspberry Pi, 100% CPU

I think Syncthing is an amazing piece of software, but I ran into problem last week.

I have a library of 10 different folders, 120000 files, 42000 directories and 428GB of data.

I thought that was a little bit too much for my RPi V1 (Syncthing 0.14.40, Arch Linux), because it constantly ran at 100%. I raised Rescan Interval to several hours (so it would finish before staring over).

After startup it took about 10-15 min to get the web GUI up, and about an hour to scan all folders for the first time. Well, that is ok, but after that it still constantly used 100% CPU despite all folders were “up to date”.

It turned out it crashed and started over. I found panic logs in .config/syncthing and error messages in ./config/syncthing/index-v0.14.0.db/LOG.

Some errors indicated Bad Magic Number and Checksum Corruption. The usual reason for this seems to be hardware problem (!?!).

I upgraded my RPi V1 to an RPi V2, with little success. Then I found that I had similar problems on another RPi V2. So after shutting down Syncthing I tried the quite scary:

  $ syncthing -reset-database      ( does not start syncthing )      
  $ syncthing                      ( start syncthing )

After several hours of scanning everything seems to work perfectly!
Let us see how long that lasts.

Eee in 2017

I came up with a possible use for my Asus EeePC 701! A challenge is to find a Linux distribution that works well with it: Lubuntu 16.04 LTS Alternative 32-bit seems good.

Lubuntu 16.04.3 is released, but for the moment I got 16.04.1 with the alternative download. After installation about 1200MB was available (I created no swap, despite warnings, since I have 2BG RAM) on my 4GB SSD.

It turned out the full upgrade (to 16.04.3) requried too much temporary space and filled up my drive. You can do two things to prevent this:

  • Mount /var/cache/apt on a USB drive while upgrading
  • Uninstall packages

When it comes to finding unnecessary packages its up to you. I uninstalled cups (no need to print), abiword (no need to write documents), gnumeric (no need to do excel-work) and many fonts (mostly thai and japanese).

Developer lost in Windows

Admittedly, I am not a Microsoft fan, but Windows is a quite fine operating system nowadays. This article is not about complaining with Windows.

This article is also not about native Windows development for Windows. That is, if you use Windows, Visual Studio and C# (or other languages native to Windows development) to produce software targeting Windows, this article is not for you.

I and other programmers use Linux, OS X or possibly BSD to develop software meant to be OS independent. Our core tools are perhaps bash and a terminal emulator. We use tools like grep, head, tail, curl, iconv, sed, bc, emacs, vim, ssh, nc, git or svn on a daily basis (without them we are in a foreign land not understanding the customs). Depending on programming language we use compilers and interpreters like gcc, python, perl, php, nodejs and sbcl. In Linux, OS X or BSD this all come very naturally but sometimes we find ourself using a Windows computer:

  1. We just happen to have a second Windows computer that we want to use
  2. Company policy requires us to use Windows
  3. We want to be capable of working in Windows
  4. We want our project to work fine in Windows
  5. Perhaps you are a Windows developer/user who need/want to do unix-like development without getting a separate computer.

This article is for you!

The good news is that basically everything you wish to do can be done with free software (also on Windows). What is also good is that you have plenty of choices of good stable software to choose from.

The bad news is that finding just what is right for you and making it feel as simple and smooth as you are used to can be time consuming, difficult and frustrating.

Embracing Windows
To be productive in Windows you should (at least to some degree) embrace Windows. One approach is to do as the Windows developers. This would mean using cmd.exe (the old DOS-shell) or Powershell, and learn/embrace what comes with it. You would perhaps install only node/php/python native for Windows and git. I encourage you to try this, but I will not write more about it.

This might be the best solution if you develop in JavaScript or Java AND basically all tools you use are part of a JavaScript/Java ecosystem. Perhaps git is the only thing you need apart from what you install with npm.

Avoiding Windows
One approach is to just use Windows to access (and possibly run a virtual) Linux (system). It can work better or worse depending on your situation. A full screen VM might be the best solution if Linux GUI tools are central to your development, or if you are anyway very used to working with VMs. SSH to a remote system might be the best solution if mobility is not a problem. However, some development gets more complicated when different things are on different IP addresses, and security becomes more relevant when everything is not on 127.0.0.1. I will not write more about this.

Make Windows Unix-like
So, our gool is to feel reasonably at home in Windows by installing what is missing. It is always tricky to divide things in clear categories, but I would say you will want a stack of four layers:

  1. A Terminal Emulator: Windows already comes with one, but chances are you will not find it good enough. I have very modest demands but I expect copy-paste to work nicely and I expect multiple tabs. This works perfectly in any default Linux desktop and Mac OS X, not so in Windows.
  2. Editor: Unless you prefer to use vim or emacs directly in the terminal you want to install a decent or familiar text editor (Nodepad or Wordpad are not suitable for serious programming).
  3. The standard UNIX/GNU tools: Windows does not come with bash, head, tail, grep, sed, vim, bc and most other tools you take for granted. The old (DOS) equivalents are simply inferior. The new (Powershell) equivalents are… well… lets just say it is a steep learning curve and your bash scripts will not run.
  4. Interpreter/Compiler: Windows does not come with gcc, python, perl, nodejs or php. However, they are most often available as a separate download for Windows. Such a native Windows version may be slightly different from the Unix-version you are used too (command line options, especially related to paths may be different).

The short version is that you can install things like Cygwin or Windows Subsystem for Linux and you might just be fine with it! Or not. If you are bored of reading, try it out now.

To make a more informed choice you need to consider what types of binaries you want to run (and perhaps produce).

Native Windows Binaries
A Native Windows binary can (with some luck) be copied from a Windows computer to another and run. To interact with Windows (and you) it uses the APIs of Windows (typically Win32). It probably expects paths to be formed like in Windows (c:\tmp rather than /tmp).

Native Linux Binaries
A Native Linux binary was typically built on a Linux system to run on that Linux system (like Debian). Until recently it would not run on Windows, however Microsoft put a massive effort into Windows Subsystem for Linux, which allows you to run Linux programs (including bash) directly in Windows 10 (only). This is not perfect though. A Linux filesystem is quite different from a Windows filesystem so access between the two filesystems is limited and may require some thinking. This is perhaps the best approach if you are targetting Linux (like development for Docker) but it is obviously a bad approach if you want your program to work on a Windows server or other Windows computers.

Hybrid / Cygwin
There is an old (as in proven and reliable) project called Cygwin. It is basically a DLL-file that translates all (most) Linux system calls into Native Windows calls. This means that the unmodified source code of (most) programs written for Unix can be compiled with Cygwin, for Cygwin, and run on a Windows computer that has the Cygwin DLL installed. There are some drawbacks. First, performance suffers (from nothing to quite much depending on what you do). Second, for more advanced software, especially with GUI or heavy on network (like Apache), the hybrid solution can feel like the worst of two worlds. Third, access to the entire filesystem is smooth, but when it comes to access rights it sometimes does not work perfectly (files created by Cygwin get weird, even broken, permissions).

Now, to complicate things, there is a project called MSYS2 that maintains a fork of Cygwin, very similar to Cygwin. Cygwin or MSYS2 can be included/embedded in other projects (such as cmder). If you install multiple unix-compability-suites on your system it can get confusing.

Choosing binary type
At first glance Windows Subsystem for Linux, or Cygwin, seem very attractive. But lets assume that we do web development in Python. If you go with Windows Subsystem for Linux you will need to run a webserver (apache, lighttpd) inside that subsystem. To me, configuring, starting and stopping services inside this subsystem is not attractive. What could possibly go wrong? Well, a lot of things. With Cygwin you can probably make Windows IIS invoke Cygwin Python (if you really dont care about performance), because running Cygwin Apache sounds creepy (it can be done though). If, on the other hand you install Python built for Windows you get the real thing. All Windows/Python documentation and forum information suddenly applies to you. But then you end up with a Cygwin shell where everything is just like in Linux, except Python is not (except Cygwin will come with Python too, so you can end up with two versions of Python, with different features).

I would hesitate to run apache inside Cygwin and even more so inside Windows Subsystem for Linux. But I always also hesitate to do anything with IIS. Perhaps the best thing is to install Apache and Python for Windows (not depending on Cygwin) and just find the tools you need to edit your files?

The same reasoning can apply to PHP, nodejs or whatever you do.

Most configurations can probably be made to work. But you just want your Windows computer as simple and standard as possible, and you want your usual Linux (or OS X or BSD) stuff just to work the way they usually do. This is really not a matter of right or wrong, it is more a matter of taste (what kind of worthless errors do you want to solve just because you are a foreigner in Windows doing stuff not the way it was really meant to be done in Windows?).

Maintainability and Management
One thing is to make it work. Another thing is that it works week after week, month after month. Also another thing is to keep your software up to date and being able to add new tools along the way. You will find that some of the software I mention in this post does not come with the Windows installer/uninstaller that you are used to.

There is something called Chocolatey for Windows, which is a package manager dealing with installing, upgrading and uninstalling software on Windows in a uniform way. I don’t know much about it, and I will not write more about it.

While unix programs typically have a .file with configuration (there are a few places to look though) Windows programs typically use the registry. When it comes to unix software adapted for Windows you never really know: registry, config file, both or… depends on? And if a config file, where is it?

While unix programs can usually be installed in the home directory of an unpriviliged user, or in /opt, programs in Windows often require administrative priviliges to spread their files a little bit everywhere.

The more stuff you try and throw out, the more garbage you have left on your computer, which could possibly interfere with a newer version of something you install in the future. Keep this in mind. One day you will install some exotic software that does not work as expected, and you dont know if some old garbage on your computer caused it.

Git
Git is a very popular version control system. Originally designed for Linux it is today (?) the officially preferred system also for native Windows development. Git is so popular (or demanding?) that you can get it bundled for Windows together with some of your favourite tools. This might be just enough for you!

  • posh-git : git for powershell
  • git for Windows : based on Git for Windows SDK
  • cmder : based on MSYS2
  • …more?

cmder
I have tried cmder and I dont like it. It is an ugly install of just unpacking a huge zip file. MSYS2 itself is hidden inside the cmder-folder, so I dont feel comfortable managing it on my own. There seems to be no upgrade strategy (except throwing it all away and downloading the latest version). Git is run from one shell (a traditional Windows shell with a lambda prompt) but a msys2/bash (identical to Cygwin) shell is started separately. I dont want to change console to run git: I run git all the time. But it might be perfect for you (many people like cmder).

Cygwin
Cygwin is nice becuase it comes with an installer (setup.exe) that is also a package manager. It has a lot of packages, and it is capable of installing things like apache as windows services. My experience is that I am too lazy downloading the latest setup.exe, and I am too lazy running setup.exe regularly. Sometimes you end up with old versions and upgrade problems.

My disappointment with Cygwin is that it comes with its own (compared to standard Windows) terminal Mintty that still does not have tabs. I also do nodejs development and nodejs is not a Cygwin package, so I need to use standard Windows node. This sucks a little because node in Windows behaves slightly different from node in Linux/OS X (particularly when it comes to where packages go) so the Cygwin experience is a bit broken when you start using Windows node and (perhaps particularly) npm.

Also, I like bash scripts and they tend to run significantly slower in Cygwin than in Linux (process forking is extremely cheap in Linux and rather expensive in Windows, so with the Cygwin overhead it can get rather slow for heavy scripts).

As I now try to update and configure my Cygwin environment for my Node.js project I find:

  • I use Cygwin wget to download setup.exe (so I get it where I want it, rather than Downloads) to update Cygwin. When I double click it (to run it) permissions are wrong and I cant execute it. It is an easy fix, but compared to OS X / Linux this is awkward.
  • I run node from Cygwin. I get no prompt (>). It turns out node.exe does not recognize Cygwin/bash as a terminal and I need to run node.exe -i.
  • Symlinks keep being a mystery. There are some kind of symlinks in Windows now, Cygwin seems to try to use them, but the result is not consistent.

For a Terminal with tabs, check Fatty below.

MinGW & MSYS
While the idea of Cygwin is to provide a Posix compliant environment on Windows the MinGW/MSYS project was about porting unix tools (perhaps particularly a gcc-based C/C++ build environment) to run natively on Windows. According to the Wikipedia page of MinGW this is pretty much abandoned.

Gow: GNU on Windows
Gnu on Windows is a lightweight alternative to Cygwin. It appears to not have been updated since early 2014 (when 0.8.0) came out (and the Windows Subsystem for Linux seems to be one reason it is less relevant). I will not write more about it.

MSYS2
MSYS2 is the successor to MSYS, and (surprise) it is based on Cygwin. I tried it quickly and I find that:

  • It seems safe to install side by side with Cygwin
  • Using the MSYS2 is very similar to Cygwin
  • Instead of the Cygwin GUI package installer, MSYS uses pacman from Arch (if you much prefer that, go with MSYS2)
  • MSYS2 has some emphasis on MinGW32 and MinGW64. As I understand it this is about being able to use MSYS2 to build native Windows software from C/C++ code (if you do this in Cygwin, you end up with a Cygwin dll dependency)

So, for my purposes MSYS2 seems to be quite equivalent to Cygwin. Expect the same annoyances as I mentioned for Cygwin above.

Windows Subsystem for Linux
If you try to run bash from a Windows 10 command line you will probably get something like:

-- Beta feature --
This will install Ubuntu on Windows, distributed by Canonical
and licensed under its terms available here:
https://aka.ms/uowterms
In order to use this feature you must have Developer Mode enabled.
Press any key to continue...

Note that this can be quite confusing if you have installed some other bash.exe on your system. If you unexpectedly get the above message, check your PATH and make sure you invoke the right bash executable.

Installation is very easy (activate Developer mode and run bash), after giving username+password you are actually good to go! If you are used to Debian/Ubuntu you will feel surpisingly at home.

I find my Windows files in /mnt/c (not too surprising).
I find my Linux home files in c:\Users\zo0ok\AppData\Local\lxss\home\zo0ok.
(copying files there from Windows did not make them appear in Linux though)

So, if you want to edit files using a Windows GUI editor, they need to be in Windows-land, and that is obviously not the optimal environment for you project.

In general it works very well though. My node services had no problems listening to localhost:8080 and accepting incoming http requests from a Windows web browser.

If you are not happy with Ubuntu or you want more control of your Linux environment you will need to do further research. Ideally, Windows Subsystem for Linux has most of the advantages of a virtual machine, but none of the drawbacks. However, depending on what you really do and need, it can turn out to have most of the drawbacks and few of the advantages instead.

Fatty
The Mintty terminal that comes with Cygwin is ok, but it does not support tabs. There are different alternatives, and a simple one is Fatty (it is really Mintty with tabs). Installing Fatty requires doing a git clone and compiling it yourself. If you are brave you can download fatty-1.6.exe from me.

The web page for fatty tells you how to make a desktop shortcut but it did not work for me. What works for me is to set Shortcut target: “C:\cygwin64\bin\fatty.exe -“. Simple as that. I think I will be quite fine with fatty, actually.

Making Fatty run Windows Subsystem for Linux was trickier (as in no success) though.

ConEmu
ConEmu seems to be the ultra powerful flexible console. After 5 minutes I have still not found out how to change the font size.

ConsoleZ
ConsoleZ is good. Under Edit->Settings>Tabs you can add your own shell types.

Cygwin:                       Shell = C:\cygwin64\bin\bash.exe --login
Windows Subsystem for Linux:  Shell = bash.exe

Apart from that, ConzoleZ is reasonably easy to configure and it stays out of your way (I hide toolbar, status bar, search bar).

Editors
I am fine with vim in the console. However, there are many fine editors for Windows:

  • Visual Studio Code (at no cost)
  • Atom
  • Notepad++

Conclusions
I have had Windows as a 2nd/3rd platform for many years and I can see that the game has changed a bit. Microsoft has started supporting Ubuntu on Windows and at the same time the native options (like MSYS) are fading away. There are reasons to think general development is getting more and more based on Unix.

I would say:

  • Posh-git : Powershell is your thing, and you don’t care about unix tools
  • Git for Windows : You want Git, but you don’t care much about other unix tools
  • Cygwin : You want plenty of choices of unix tools in Windows
  • MSYS2 : You like pacman (Arch) or you want to build native Windows C/C++ binaries using free software
  • Windows Subsystem for Linux : You have a Windows 10 computer but you want to keep your Linux development separate from Windows

If you use Cygwin and just want tabs, get Fatty. Otherwise ConsoleZ is good. Chocolatey is more a Windows power user tool than something you need to provide unix capabilities.

In the past I have mostly been using Cygwin (with mixed feelings). Lately, when I have heard about the options (cmder, poshgit, Git for Windows, MSYS2) I have got a feeling that it is rather hard to configure an optimal environment. Now however I have come to realize that the differences are not very big. Most options are hybrids based on Cygwin and/or with Cygwin embedded (perhaps in the name of MSYS2). For Windows developers not used to Unix it is good with things like Git for Windows that just come with the basic Unix tools with no need to think about it. For developers with a Unix background it makes more sense to run Cygwin and MSYS2 (or Windows Subsystem for Linux). The days of unix tools built natively for Windows are over, and it is probably a good thing.

What you need to think about is your compiler, interpreter and/or web server.

SonarQube 6.5 – Mac OS X – Installation problems

It seems SonarQube 6.5 does not work with JDK 9. Java 8 upgrade 144 works fine.

There is no automated way to uninstall JDK 9 properly, but you can have different Java side by side. This is how to pick Java version.

export JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk1.8.0_144.jdk/Contents/Home

After that you can run

sonar.sh start

as usual.

Can not log in to SonarQube 6.5 on Mac OS X with default password
With JDK 9 authentication with default user/pass admin/admin fails. It turns out the error HTTP code is 500, not 401, which made me suspicious.

Peculiar Compiler Optimizations

My teacher in a High Performance Computing class once told me not to confuse the compiler. This was in the late 90s, and SGI C and Fortran compilers were supposed to replace entire blocks of code with highly optimised implementations. As long as the compiler understood your intentions.

I have never discovered this, but yesterday perhaps! Read on.

I have been playing around with LISP, solving Project Euler challenges on Hackerrank. For problems 44 and 45 I decided to do Binary Search (which afterwards turned out not to be so smart, but that is another story) and took the implementation from Rosetta Code (the iterative one).

Binary search is about finding an element in a sorted array by starting in the middle, and jumping left or right, cutting the remaning array in half each time.

In my case I decided just a part of the array was worth searching so instead of searching the entire array [0..length] I wanted to search up to the Nth element [0..N]. Searching fewer elements should be faster, so I improved the binary search function to take an additional argument: hi. For SBCL (Steel Bank Common Lisp), this surprisingly had horrible effect on performance.

Benchmark Results
The results for different algorithms, different machines and different LISP implementations follow. The RPi V1 runs Arch Linux, Clisp comes with Arch, SBCL is downloaded from SBCL webpage. The RPi V2 runs Raspbian and SBCL that comes with the distribution. The Celeron runs Ubuntu that comes with SBCL. The MacBook Air runs OS X and SBCL is downloaded separately.

 (times in seconds)             Array Size Standard Optimized Recursive    C -O2
================================================================================
RPi V1  ARMv6 700MHz  Clisp 2.49      5000    640       633       720
                      SBCL  1.3.12    5000     15.6      27        34       0.95
RPi V2  ARMv7 900MHz  SBCL  1.2.4     5000      6.2      16        17       0.31
                                     20000    110       293       300       5.8
NUC Celeron J3455     Clisp 2.49     20000    765       762       720   
                      SBCL  1.3.3    20000      8.3      16.7      18.0     1.0
MacBook Air i5        SBCL  1.2.11   20000      4.0      11.5      12.3     0.75

A very slight “optimization” turns out to have very negative impact on performance for the quite fast (compiled) SBCL. I can’t imagine any other explanation than SBCL replaces the standard binary search with optimized code rather than executing my program. For Clisp the optimization actually works quite as would be expected and the recursive code is actually the fastest. On the Celeron, Clisp and SBCL behaves completely opposite.

Comparing to C
The other week I had the feeling (SBCL) LISP was fast and decided to compare LISP to C. This time I had the feeling that LISP was rather slow so I ported my test program to C (basically line by line). Well, I found that SBCL is actually pretty fast (especially on x86/x64), and C was faster only thanks to -O2 on some systems. -O2 actually made the C-program more than 5 times faster: perhaps also the C-compiler replace the entire binary search?

The Test Program
The code follows. The only difference between Standard and Optimized is the single line that is commented out (with ; in LISP) selecting which binary search to run (the length of the function name does not explain the performance difference).

The program creates an array of length N and populates it with values by the formula n(n+1)/2. This takes little time. It then checks for values 10,20,30… if the values are found in the array (using binary search). In this program the entire array is always searched, not taking advantage of the extra parameter (although the optimized version does not need to find the length of the array every time called).

(defun binary-search (value array)                       ; Standard 2 lines
    (let ((low 0) (high (1- (length array))))            ;
        (do () ((< high low) nil)
            (let ((middle (floor (+ low high) 2)))
                (cond ((> (aref array middle) value)
                       (setf high (1- middle)))
                      ((< (aref array middle) value)
                       (setf low (1+ middle)))
                      (t (return middle)))))))

(defun binary-search-optimized (value array hi)          ; Optimized 2 lines
    (let ((low 0) (high hi))                             ;
        (do () ((< high low) nil)
            (let ((middle (floor (+ low high) 2)))
                (cond ((> (aref array middle) value)
                       (setf high (1- middle)))
                      ((< (aref array middle) value)
                       (setf low (1+ middle)))
                      (t (return middle)))))))

(defun binary-search-r (value
                        array
                        &optional (low 0)
                        (high (1- (length array))))
  (if (< high low)
      nil
      (let ((middle (floor (+ low high) 2)))
        (cond ((> (aref array middle) value)
               (binary-search-r value array low (1- middle)))
              ((< (aref array middle) value)
               (binary-search-r value array (1+ middle) high))
              (t middle)))))

(defun formula (n)
    (/ (* n (+ n 1)) 2))

(defun init-array (n)
    (let ((arr (make-array n)))
        (loop for i from 0 to (1- n) do
            (setf (aref arr i) (formula (1- i))))
        arr))

(defun solve (arr n max)
    (let ((ret 0))
        (loop for i from 10 to max by 10 do
            (if (binary-search i arr)                     ; Toggle code used
;           (if (binary-search-r i arr)                   ;
;           (if (binary-search-optimized i arr n)         ;
                (incf ret)
                Nil))
        ret))
            
(defun main ()
    (let ((n (read)))
        (let ((arr (init-array n)))
            (format T "~D~%" (solve arr (1- n) (aref arr (1- n)))))))

(main)

Since I am a very novice LISP programmer I appreciate any feedback. The code above does not solve Project Euler 44 or 45, it is much simplified to test binary search. Initially I wrote code that relied on recursion rather than loops but I exceeded the stack size and ended up with loops (according to what I read, loops rather than recursion is the preferred style of Common Lisp).

Conclusion
Well... optimization is hard, and dont make any assumptions. As I have found many times before, what makes code faster on some platforms can make it slower on others. When it comes to optimizing SBCL and compiled LISP much experience is required, and dont forget to measure!

Upgrade windows hard drive

So, you have a Windows 10 (this probably applies to Windows 7 and forward) computer and you want to replace your system drive because you have a bad feeling about the health of the current drive, or you just want a larger SSD.

If you start searching on Google (or Bing) for this, you will get so many crappy answers: plenty of companies want to sell you tools, and Microsoft provides so much information that is hard to make any sense of. This is a simple and (quite) safe procedure that worked for me.

What you need

  1. A new hard drive, larger than the previous one
  2. A USB key, at least 8GB
  3. A USB hard drive, with enough space for backing up all your files

All drives should contain nothing of value as they will all be reformatted in the process.

Steps

  1. Create a Recovery Drive to the USB key (2)
  2. Create a System Image to the USB hard drive (3)
  3. Turn your computer off
  4. Replace your current system drive with the new one (1)
  5. For safety, unplug drives that you don’t want restored
  6. Start computer from your Recovery Drive (2)
  7. Choose Advanced
  8. Plug in System Image drive (3)
  9. Restore System Image
  10. Restore to your new hard drive (1)
  11. Profit!

This is a safe way to upgrade hard drive because:

  • You always have your original system intact and you can put your old hard drive back if anything goes wrong.
  • You completely only use standard Windows tools. From Windows/Microsoft perspective your original hard drive broke, you were smart enough to have proper backup, and you simply restored your backup.
  • It is anyway a good thing to always have (2) and (3) in case of disaster.

Problems, Annoyances, Caveats
The process is quite annoying.

  1. Just finding out where in Windows to create Recovery Image and System Image is a pain.
  2. Creating the Recovery Drive is very slow, despite you have a fast USB Key
  3. I did not click Advanced after starting the Recovery Drive. That ended up formatting a non-system-drive that was plugged in (I realised my mistake too late).

References
Howtogeek

Playing with LISP and LISP vs C

Lisp is fun! Well, since I first knew about Lisp I was fascinated, but I have found it hard to learn Lisp and to play with it in a meaningful way. A few years ago I wrote about it here and here. As usual, the first steps of learning something new can be the hardest.

Occationally I use Hackerrank to find programming challanges to solve for fun. I particularly like the Project Euler competition. I find it particularly good for trying out new languages: you get a “meaningful” challenge, a simple environment prepared in your web browser, and automated test cases. So, this time I didn’t waste my time trying to find the right Lisp implementation for me, I just started hacking on Project Euler 38 and 39 on Hackerrank.

Problem 38 was quite simple, but 39 was more interesting. When I had solved it, I found my implementation was not at all fast enough, so I started experimenting locally (the Hackerrank environment is not optimal for tweaking, optimization and debugging).

Choosing a (Common) Lisp implementation
There are quite many Common Lisp implementations out there. The one Hackerrank uses is SBCL. That is clearly the Common Lisp implementation I would recommend (based on my little experience) if it is available for your platform.

I installed SBCL with apt-get in Ubuntu. I also downloaded binaries directly for my Mac OS X computer and my Raspberry Pi (v1) running Arch linux. Installation is a bit non-standard, but you can actually run it without installing (just execute run-sbcl.sh in downloaded folder).

I also tried clisp and ecl, none of these could deal with the memory usage (stack size) of my program. For clisp I found no way to manipulate stack sizes at all. For ecl I made some progress but I could not make it run my program.

SBCL is a Lisp compiler, and it produces fast and efficient code. I later compared it to C.

Project Euler 39
Project Euler 39 is basically about finding integer solutions to Pythagoras theorem. For a given, large, perimeter, how many right triangles are there? For example:

300000^2 + 400000^2 = 500000^2

This triangle has a perimeter of 300000+400000+500000=1200000. What other values for a and b so that

a + b = 700000
a^2 + b^2 = 500000^2

are there? The Hackerrank challenge requires you to work with perimeters up to 5000000. If you implement a solution, a few things to immediately note:

  • The squares wont fit in a 32bit integer. They will fit with no loss of precision in the 53 bits of a 64 bit double and they will also fit in a 64 bit integer. (This matters not for Common Lisp)
  • If you want to do recursion (and of course you want when you code Lisp) it will be millions of recursion steps, which will be a challenge to the stack size. (This also turned out not to matter for SBCL)

The Lisp implementation
It turned out that the SBCL compiler optimized the recursion is such a way that the memory usage was quite low. SBCL successfully runs my program on RPi/Arch, Intel/Ubuntu and Intel/OSX with quite reasonable memory usage.

Since this is about learing Lisp I wanted a 100% functional programming implementation. Only pure functions. A lot of my code is about generating, modifying and testing triangles. A triangle (a b c) can obviously be represented as a Lisp list (a b c) and this was my first implementation. Then if you want to read a, b or c from a list abc, or create the list from a, b and c, you can do:

  a: (car abc)
  b: (car (cdr abc))
  c: (car (cdr (cdr abc)))

abc: (list a b c)

I found this cumbersome. It became a lot of list-to-variables and variables-to-list overhead (I didnt care so much about performance, more about my code readability). I learnt that Lisp functions can return multiple values using value and that you can bind them with multiple-value-bind and use them as arguments to a function using multiple-value-call. This felt functional and pure enough, and it made my code 25% faster than the car/cdr pattern above.:

; a (stupid) function returning a triangle as three values
(defun get-345-triangle ()
  (values 3 4 5))

; a function calculating the perimeter of triangle (from a function)
(defun triangle-perimeter-1 (tri-func)
  (multiple-value-bind (a b c) (funcall tri-func)
    (+ a b c)))

; and in this case you dont need to bind, you can use + directly
(defun triangle-perimeter-2 (tri-func)
  (multiple-value-call #'+ (funcall tri-func)))

; now this works
(triangle-perimeter-1 #'get-345-triangle)
(triangle-perimeter-2 #'get-345-triangle)

Since I am a very inexperienced Lisp programmer I appreciate suggestions for improvement.

Performance of Lisp
My final Hackerrank submission of Lisp code executes in about 4.5 seconds on my Intel i5/Ubuntu. It takes about the same time on the Hackerrank web page, which is fast enough to pass all tests. On the Raspberry Pi v1 (ARMv6 @700 MHz) it takes more than 700 seconds. My intuition told me that 4.5 seconds was very good. This made me ask two questions. How would Lisp compare to C? And why is the ARM more than 100 times slower, how would that compare in C?

The C implementation
My ambition was to rewrite Lisp to C line by line. So my C-program has exactly the same functions which take almost exactly the same arguments. All calculations are identical and performed in exactly the same order. The C-program relies entirely on recursion instead of loops (just like the Lisp program). However…

Functions in C can not return multiple variables. While Lisp had values I decided to use a reference to a struct in C:

(defun get-a-triangle()
  (values x y z))

void get_a_triangle(struct triangle *t) {
  t->a = x;
  t->b = y;
  t->c = z;
}

If the C-triangle struct is a local variable on the callers stack the difference is quite small (from a practical point of view, from a theoretic strict functional programming perspective its a different story).

Numbers in Lisp have arbitrary precision integers and floats make no difference. So, when porting to C, I had to pick numeric types. For most purposes, int32_t was good enough. But, for the purpose of calculating Pythagoras theorem higher precision was needed (as I wrote above, the 53 bits of double, or 64 bits of int64_t are good). So I ended up with 5 versions of the C-program (to compare performance):

  1. All 64-bit integers
  2. 32-bit integers, 64-bit for “triangles”
  3. 32-bit integers, double for “triangles”
  4. 32-bit integers, 64-bit only for pythagoras calc
  5. 32-bit integers, double only for pythagoras calc

(In cases 2,3 the struct triangle has int64_t/doubles properties, and all manipulations and calculations on triangles use these datatypes. In cases 4,5 everything is int32_t, except the internals of a single function, which casts to higher precision before doing its calculations.)

The C-program requires a significant stack size. The stack size can be obtain and changed like (numbers in kb, all values given with ulimit -a):

$ ulimit -s
8192

$ ulimit -s 100000

For my program, a stack size much higher than 8192 is needed (see below). It seems impossible to get large stack than 64Mb in Mac OS X, so my C program could never run there.

Benchmark findings
All C-programs are compiled with gcc -O2.

 CPU            MHZ      SBCL        64     32/64  32/double   32(64)  32(double)
==================================================================================
Time (s)
 i5-4250U 1300-2600       4.5      1.52      1.52      1.60      1,54      1.58
 ARMv6          700      ~715        85        83        45        42        39
 ARMv7          900       357        23        21        13        12        10

Max Res (MB)
 i5-4250U                  41       103       103       103       103       103
 ARMv6                     50       220       210        79       110        76
 ARMv7                     57       180       160        87        97        62

This is not too easy to interpret! The ironic thing is that the fastest thing on the x64-cpu (64-bit integers everywhere) is the slowest on the ARMv6. However, the fastest option on the ARMv6 (32-bit everywhere, and when absolutely needed, use double) is almost the worst on the i5 CPU.

When it comes to the 64-bit i5, it basically does not matter what datatypes you use.

When it comes to the ARMv6, the most important thing is to not store the triangles as int64_t. The strange thing here is the stack sizes. Why does it double (compared to x64) when triangles are stored as int64_t? And the doubles, why do they reduce stack size so much (where are all these doubles actually stored)?

The time command gives max resident memory usage. If I set ulimit -s 128 the first two programs fail (with Segmentation fault 11), and the last three ones succeed, on the ARMv6.

I have found before that the performance of the ARMv6 suffers because of its slow memory and small cache. It is quite possible that the poor performance of the ARMv6 compared to the i5 is related to its slow memory, and the recursion (and stack memory) heavy algorithm.

Finally, SBCL in x64 has very good performance even compared to C (however, an iterative C-implementation, fitting completely in cache, would probably be faster). Note that I am a novice Lisp programmer and this is a math heavy program where the generic number type of Lisp will come at a cost. On the ARMv6, Lisp performance suffers much more.

Windows stack size limit
For Windows, stack size limit is set in the binary, not in the shell. With Cygwin/GCC use the flag -Wl,–stack,1000000 for one million bytes. Note that these are options passed on to the linker.

Future investigations
And I am curious about how much faster a minimal-memory-footprint loop-based C-program would perform.

The source code
Since this code solves a problem in Hackerrank I hesitate to publish it. If you want it for any other reason than just running it on Hackerrank let me know.