Clifford Wolf's Blog

For Yosys I was long stuck with std::set<> and std::map<> as primary container classes because one of the goals of Yosys is to produce identical outputs for the same input across all compilers and architectures. (A goal that is not reached yet btw, but I'm working towards it.) The std::unordered_* versions of those containers don't even make guarantees about identical order of iteration between two processes executing the same code. For my taste it is to easy to make a crucial programming mistake and accidentally iterate over one of those containers in a situation where the order of iteration has a subtle influence on the program output. So I've created my own containers that have the guarantees I need for Yosys. My hashlib::dict<> is a replacement for std::unordered_map<> and my hashlib::pool<> is a replacement for std::unordered_set<>. (My containers also require the programmer to be more explicit when using pointers as keys and they utilize an interface for creating hash values that integrates better with Yosys's core data structures than the std::hash()-scheme does.)

To my surprise my straight-forward textbook implementation of a hash table is significantly -- sometimes over 2x (!) -- faster than the STL versions of the same containers. I guess it pays off if you do not design your data structures around strange interfaces such as bucket iterators.. (Did anyone ever use them, btw?)

The picture below shows the results of this simple benchmark (also includes my hashlib.h library). Because I replace the ordered STL containers directly with my unordered versions, I also included the ordered STL containers in the benchmark. The labels "sparse" and "dense" in the figures below refer to the used alphabet. The "dense" alphabets are slightly easier to hash. For each of the 240 data points the benchmark executed 20000000 operations (insert, update or delete), first filling the container to the specified size (in number of elements) and then inserting and deleting while keeping the size around that value (within +/- 1000 entries and +/- 10%). In the tests for the map containers int was used as value type. (click image to enlarge)



PS: Clang version: 3.4-1ubuntu3, GCC version: 4.8.2-19ubuntu1

I bought an Acer Chromebook 13 CB5-311-T6R7 (the one with the NVidia Tegra K1 ARM CPU) to run it in a dual-boot configuration with Chrome OS and Ubuntu. I've used a slightly modified version of the modified chrubuntu script from here to install ubuntu. My version of the scripts and a writeup of the install procedure can be found here.

Update 2015-01-20: I have now updated my install script to address the freeze up issue discussed in the comments below. See my comment for the details of the fix used.

Update 2015-08-28: I have now updated my install script to use the current NVidia "Tegra for Linux" release, Tegra124_Linux_R21.4.0.

After over 8 years of service my old server had a fatal crash three days ago. The disk controller died and killed both disks (RAID1) in the process. Fortunately my backup strategy worked like a charm and I only lost about 6 hours of incoming email (so if you sent me a mail in the morning of Thu 4th December 2014: please try again).

Following an ancient tradition (of over 15 years) the new server is called phoenix.clifford.at, like the ones before it.

I have a backup of all data from the old machine, but I decided not to re-setup everything that ran on the old server. Especially I did not re-setup the shell logins I gave away over the course of the last 15 years. I also decided not to re-setup the services related to ROCK Linux. Please contact me if you had data on the old server that you want back or had a shell account that you were still using..

BTW: The backup solution I'm using is a simple shell script I wrote over 10 years ago and am using ever since. I've now put it on github, just in case anyone of you is interested: https://github.com/cliffordwolf/rsbak3