Sleep Sort in OTL

I found Sleep Sort so ingenious (in the mad genius way) that I just had to implement it using the OmniThreadLibrary framework.

The code is now shorter than Serg’s original implementation and it’s … wait for it, wait for it … even faster! Twice as fast as the original, actually! Now that I call an improvement!

The code below carries not copyright nor copyleft and can be used in any occasion as long as you don’t blame me for getting fired or any other problems in your personal or professional life it may cause.

Lock-free vs. Locking: Rematch!

My article on lock-free vs. locking data queues was well-received but there were also some comments and complaints. To answer the critics (your comments were all very appreciated!) and to fix some issues with the previous test I’ve decided to stage a rematch.

New contestants

Both Iztok and Chris have provided me with new versions of their queue implementations. Iztok’s code was tuned a little and changed to use TOmniValue instead of TAnyValue for better comparison with TOmniQueue. Chris has created three different variants of his code.

OmniThreadLibrary Needs YOU!

That is, if you are a C++Builder programmer and want to help an open source project.

The problem with OmniThreadLibrary and C++Builder is very simple – I’m not using it. (The C++Builder part, obviously.) Therefore I’m not checking for compatibility with C++Builder and I cannot fix the stuff if it doesn’t work. (In C++Builder.)

And now a user reported that the OTL doesn’t compile. In C++Builder. And I don’t know how to help him. With his problems. In C++Builder.

[BCC32 Error] DSiWin32.hpp(36): E2257 , expected

[BCC32 Error] DSiWin32.hpp(346): E2040 Declaration terminated incorrectly

[BCC32 Error] OtlCommon.hpp(305): E2238 Multiple declaration for 'TOmniValueContainer::Item'

[BCC32 Error] OtlCommon.hpp(304): E2344 Earlier declaration of 'TOmniValueContainer::Item'

[BCC32 Error] OtlSync.hpp(33): E2113 Virtual function '_fastcall IOmniCriticalSection::Release()' conflicts with base class 'IUnknown'

[BCC32 Error] OtlSync.hpp(74): E2113 Virtual function '_fastcall IOmniResourceCount::Release()' conflicts with base class 'IUnknown'

Is there a nice soul out there that can tell me how to fix the problem? (Or even better, who can make sure that the OmniThreadLibrary compiles with C++ Builder.) Your fixed will be gratefully imported into the main development branch and you’ll earn an eternal fame.

Lock-free vs. locking

For the past few days I was running tests on three different queue implementations – one lock-free, one based on Delphi’s TQueue<T> and TMonitor and one implemented using critical section and linked list. For a good measure I’ve also thrown a blocking wrapper around the lock-free queue into the mix. [Mostly because I’m using it a lot (it has useful features for multithreading work) and I wondered how much time penalty it adds to my applications.]
During that time I’ve discovered a showstopper bug in TMonitor which practically made TSimpleThreadedQueue useless when using more than one reader. Still, I’m including partial results for that implementation too, as they provide a good comparison.

TMonitor bug?

When Chris Rolliston implemented a simple threaded queue class using TMonitor, I was quite ecstatic. Finally I will be able to compare my lock-free queue with a threaded implementation! (That’s something I wanted to do for a long time but I never found a willpower to write a locking queue.)
My elation continued while I was coding my test app and while I tested my own queue. And then I plugged in Chris’ queue and … everything went downhill :( Immediately, my test app started crashing. At first it looked like the bug was in Chris’ code, but when I enabled debug DCUs, debugger pointed to a very unlikely location – TMonitor. Unlikely because of two reason – because I know that Delphi people take quality to the heart and test the code and because I know Allen is an experienced guy who writes excellent code.

TDM Rerun #17: Put It In A Tree

Hierarchical data appears everywhere and most of the time it must be rebuilt from simple non-hierarchical storage. Think about mail, news, CVS repositories and databases, not to mention groupware and chat forums. Trees are everywhere.

- Put It In A Tree, The Delphi Magazine 118, June 2005

This article dealt with thread sorting, an algorithm that takes a number of items connected with parent-child relationship and puts them into a tree so that they can be displayed in a nice structured way. The ideas and implementation are still perfectly valid.

Links: article (PDF, 82 KB), source code (ZIP, 241 KB).

Divide and Conquer (in parallel)

One of the latest additions to the high-level OtlParallel constructs, Fork/Join, was implemented just before ADUG 2011 and presented there for the first time. Shortly after the ADUG I improved the Fork/Join a little but then forgot to blog about it as I was busy implementing Parallel.Async and Parallel.TaskConfig. Sorry :(
Fork/Join helps you solve just one class of problems, but it is an important one – the problems that can be solved by so-called Divide and Conquer algorithm.
For deeper discussion of D&C, read the Wikipedia article linked above. What interests us is that D&C works by subdividing the problem. Instead of trying to solve the big problem, we divide it into many smaller problems and then we try to solve them. Those subproblems may again be too big and have to be subdivided even further. The process continues until the subproblems are small enough that they can be solved easily.
Of particular interest to us are D&C algorithms where subproblems can be solved in parallel.

Configuring background OtlParallel tasks

High-level OmniThreadLibrary parallelism (i.e. the OtlParallel unit) is great when you are running mostly independent parts of code but what can you do when you want to communicate with the main thread from a task?
A few weeks ago my answer would be along the lines of setting communication channel manually or dropping down to low-level parallelism (i.e. the CreateTask) but both are very complicated solutions. There was certainly a room for better solution.
Since the release 910, released on April 17th, OtlParallel contains much simpler way to configure tasks and to set them up for communication with the owner.

Simple background tasks with OtlParallel

While there’s a simple way to execute one-shot background threads with the low-level OTL API (by calling CreateTask), there is no such high-level function in OtlParallel. At least, there wasn’t one until release 899 was committed to the SVN. (Incidentally, that happened 11 days ago but I was silent about it because I was working on another feature – TaskConfig – which will be completed “really soon now”.)
In short, Parallel.Async accepts an anonymous method, normal method or procedure (all of them must be without parameters) and executes it in a background thread. That’s all.

ADUG 2011 Slides

My presentation from ADUG 2011 is now online at http://www.thedelphigeek.com/p/presentations.html.

Check out the handouts document as it contains lots of my previous writing on OmniThreadLibrary (high-level stuff) neatly collected and organized into one document.

Delphi Down Under

This year’s Australia Delphi User Group symposium is a two day event with sessions in Melbourne and Sydney. The first of those – the Melbourne session – happened today. We met in the John Scott Meeting House at the La Trobe university.


Turnout was quite big – nearly 80 very attentive listeners.

GpProfile on Google code

You may know that lifetime ago I developed fairly successful Delphi profiler called GpProfile.

You may also know that it kinda slipped into oblivion and that it can’t correctly profile modern Delphi code (it is a source instrumenting profile, i.e. it changes your source code so it can be profiled).

You may know all that but I’m fairly sure that you don’t know that GpProfile now works for all Delphis up to XE! How can I be so sure? Because I only learned this a short time ago!

Антон Алисов (Anton Alisov) was brave enough to step in, update the code and create the Google code archive. Go Anton!

In case you’re still using GpProfile (or just want to find out why it was one of most popular Delphi profilers), visit gpprofile2011 project on Google code.

Synchronize comes to OmniThreadLibrary

This just came in:

• IOmniTaskControl.Invoke(procedure begin … end)
• IOmniTaskControl.Invoke(procedure (const task: IOmniTask) begin … end)
• IOmniTask.Invoke(procedure begin … end)

Still missing:

• IOmniTask.Invoke(procedure (const task: IOmniTaskControl) begin … end)

Parallel for implementation [3]: Output

In the previous two installments I’ve tried to give a little insight into how OmniThreadLibrary’s Parallel ForEach is implemented (part 1 – Overview, part 2 – Input). Today I will conclude this short series with the description of output ordering – or what is know in the OTL as the .PreserveOutput modifier.

Ordering is usually used together with the .Into modifier. The reason lies in the integration between the Parallel infrastructure and your parallel code (the one that is executing as Parallel.ForEach payload). In the “normal” foreach statement, output from this parallel payload is not defined. You are allowed to do whatever in the foreach, to generate any output (in case you need it) but Parallel will know nothing about that. Therefore, the OTL has no ability to preserver any ordering because – at least from the viewpoint of the library – the parallelized code is producing no output.

OmniThreadLibrary Down Under

I’m very excited to announce that OmniThreadLibrary will appear before the Australian public in this year’s ADUG Symposium!

This year’s symposium will happen in Melbourne on 24th and in Sydney on 25th of March.

The title of my presentation will be “Getting full speed with Delphi?” and will cover multithreading programming and high-level OmniThreadLibrary stuff.

Getting full speed with Delphi
(Why single threaded is not good enough?)

In the last few years, the traditional approach to speeding up programs ("We'll just wait for the next generation of hardware.") doesn't work anymore.

In this talk, we'll see why Delphi programs use only 12.5 % CPU on a modern machine and what we can do about it.

The session will show you how to make murky waters of multithreading accessible to every Delphi developer with the help of open source OmniThreadLibrary.

In case you want to meet with me and discuss multithreading programming (or anything else, including life, universe and everything), I’ll be available before the Melbourne and after the Sydney event.

How to crash Delphi compiler in four easy steps

Step one

Start Delphi XE.

Step Two

Create simple project.

Parallel for implementation [2]: Input

In my last post, I’ve presented an overview of classes hiding behind the parallel for implementation. Today I’ll focus on the input part of the parallel for – the part that fetches values the loop is iterating over and passes them to parallel tasks. More specifically, I’ll present source providers, data managers and local queue.

Parallel for implementation [1]: Overview

Aeons ago I promised to write a blog post about all the magic that happens behind the scenes in Parallel.ForEach. That never happened (sorry). I was busy will other stuff and I had to put it on the backburner.

Today is the day to fulfill that promise.

This article starts the journey that will (hope, hope) explain the murky waters of parallel loop data management. Three parts are planned – Overview (which you are reading now), Input and Output.

Even if you are interested in parallel programming, you may think that such low-level stuff is of no interest to you. Well, you may be right, but let me state three reasons why you should read this three-part series.

1) Because you will then know what the OtlDataManager unit is good for and will be able to use it in your application.

2) Because it’s an interesting topic ;)

3) So I can convince you that Parallel.ForEach is better than home-brew multithreaded parallel loops and that you should always use OmniThreadLibrary ;)

Ready?

Delphi on wide screen

A lifetime ago when I was still programming on two 1280 × 1024 monitors I’ve published a post about the IDE layout I was using at that time (in Delphi 2006).

I was always saying that there’s only one reason why a programmer should use two monitors – because (s)he has no place for the third one! So when the opportunity knocked I did the same – cleaned up some place on the desk and installed a 1920 × 1200 monitor in the middle.

GpLists and GpStructuredStorage update

GpLists 1.49: Implemented TGpGUIDList, a TGUID list.

GpStructuredStorage 2.0c: Uses GpStreams instead of (deprecated) GpMemStr.

Erik Berry fixed GpTextStream and GpLists to compile with Delphi 6; those changes were committed to SVN only.