I’ve implemented the first comparative benchmark. It’s for the freelist. The locking based freelist simply using a mutex. (I can in future also do further locking variants, such as a spinlock).

These are the results, and they’re an eye-opener!

Release 7 Lock-Free Freelist Benchmark #1
CPUs,total ops,mean ops/sec per CPU,standard deviation,scalability
1,302325258,30232526,0,1.00
2,297807034,14890352,27333,0.49
3,110733252,3691108,760105,0.12
4,107517282,2687932,143228,0.09

Release 7 Mutex Freelist Benchmark #1
CPUs,total ops,mean ops/sec per CPU,standard deviation,scalability
1,23123970,2312397,0,1.00
2,1501904,75095,335,0.03
3,1683186,56106,17,0.02
4,1662666,41567,37,0.02

We see lock-free is 10x faster with one core; and is 100x faster with two cores! (the three and four core rows are to be ignored; they’re hyperthreading cores, not real cores).

However, we still see that scalability for lock-free with two cores is < 0.5, so you still get more work done with one core than two. This might be due to live-lock. Backoff is on the to-do list.

A note on the mutex freelist. It -is- the lock-free freelist; the source code was copied, the type names are changed (prefixed with an ‘m’) and that where the lock-free freelist uses lock-free instructions, the mutex freelist obtains a mutex, does the necessary pointer manipulation, and then releases the mutex.

The benchmark is identical in both cases, because it is the same benchmark; it is now given pointers to functions. For the lock-free benchmark, those functions point to the lock-free freelist functions (new, delete, push and pop) and for the mutex benchmark, to the matching mutex freelist functions.

First code draft complete – code compiles. No testing yet :-)

Have a singly linked list using them.

All of the other existing data structures (all four, lol) can be rewritten using them. I plan to keep the non-HP stuff, at least for a while and add the HP stuff beside it.

When/if that all works, next most urgent thing is to finish sorting out the tests, so they’re all of the pass/fail type; the stack test is a ugly blot on the landscale.

I may also implement a first benchmark where a liblfds data structure is implemented using locks, so lock-free/locked performance can be compared.

So, forgot what I was saying about mutexes; I forgot – there’s no easy way you can simply stop/start threads.

I have finally (been busy) duplicated the problem/solution for the freelist popping test bug. That is now release 6, known issue 6. The fix is to change the type of a variable in the test from unsigned int to atom_t.

I was looking again at SMR, via hazard pointers. I see a publically available C++ library using this, and I think JSR 166 uses it, too. So, I’m going to implement.

Recently, the site has been subject to automated spam. The forum sees new posts, which are spam, the blog sees comments which are spam, the wiki sees new pages and the destructive replacement of existing pages, with spam.

The spam consists of short pieces of garbage words (random characters), interspaced with URLs.

As such, the forum now requires a captcha for anon posting, the wiki has disabled anon editing and the blog requires me to check comments prior to them being published.

The freelist bug turns out to be a problem with the test.

Basically, I forgot that unsigned int is still 32 bit on 64 bit platforms…I still remember the notion that an int is the natural length for the platform (e.g. you’d expect 64 bits on a 64 bit CPU). I was passing the address of an unsigned int into a function which expected the address of a void pointer and so was writing 64 bits onto a 32 bit variable.

My test platforms have been 64 bit Windows (which should have shown the problem) and two 32 bit Linux (one Intel, one ARM) (which should not).

So, I need to go over the tests and fix them up with the correct types.

I’ll shortly be adding a known-issue entry for this, in the wiki.

I still also need to make some proper tests for the singly linked list.

The problem with the test is serious enough that a new release really should be made, but I really don’t want to make a release without some new functionality.

As such, I’m thinking of a lock-free mutex. I blogged about condition variables before, but they in their fully implemented form are not possible without a lock-free list.

However, a more limited form, without counters – e.g. a mutex – is possible using a queue, which is available.

So basically, you instantiate a mutex, any number of threads can wait on it and then when it’s signalled, they all wake up. All done lock-free, in user-mode.

The problem however comes with making threads wait. Ideally, you just want to put the thread to sleep. You can do this in Windows, but not in pthreads. In pthreads, all you can do is yield. That’s ugly and I’m not sure what to do with it or about it. It is functional – you can implement a solution that way, where a waiting thread, when it wakes up, will check to see if it’s been signalled and will yield if not – but it’s not exactly yummy tasty software, you know?

So…

As you can see, the site has moved from a top menu with IFRAMEs to a side menu with a FRAMESET. This is a compromise – you see, what I wanted was a single page, no frames of any kind, with the menu at the top. The problem is that the wiki, forum and bugzilla generate their own full pages – so how do you get your menu in there? not to mention Blogger being on a different site completely…

I figured a way to get the menu in there (apache module finding the tag and adding stuff immediately afterwards) but man, there’s just so many ways that could go wrong that it was not viable.

There were two problems with the original site; firstly, the menu tabs used XMLHTTPRequest to load pages, so the browser couldn’t know they were links and so you couldn’t right click and open in a new tab. Secondly, IFRAMEs are always a pain, since they scroll differently to the rest of the page.

So, for now, just to make the site more usable, the menu is on the left. The site is a FRAMESET, so it’s not perfect, but the menu tabs are links, so you can right click and open in a new tab. Also, since the main frame is now a column, scrolling is more natural.

I’ve also moved over to WordPress. Where Blogger was on another site, I couldn’t insert new markup after the tag (since it wasn’t being emitted by my Apache server). So I installed a local blog. Now I don’t need it, but it is I feel nicer to have the blog local rather than remote, so I’m keeping it.