The overhead of traditional locking is indeed a major problem with existing
programs today, but the chip makers like Intel are not the problem when it
comes to parallel execution of code - they can only help with some
guaranteed atomic instructions and even these will generally be far slower
than the normal ones.
The problem lies with the algorithms in common use: the latest shift in the
past few years has been to focus on finding provable parallel versions of
the traditional structures needed. This can be seen by a perusal of the past
few years of Phd papers and other research papers along with topics for
conferences.
The strategy employed in the recent papers is to focus on a single
traditional structure (e.g. a linked list) and attempt to come up with a
suitable multi-write/multi-read algorithm for managing it before finally
proving it mathematically (or trying to J).
That this is often very difficult is indicated by the fact that a number of
peer reviewed papers have made it into publication/conferences even though
they were later found to be wrong.
(Incidentally, memory management algorithms also depend on these common
structures - however, something like Hoard is actually relying on per-thread
information to help with avoiding taking locks and appears not to take
advantage of some key new papers out there right now, something that may
change. In fact, if you simply use a standard Windows XP non-locked Heap one
for each thread you will always beat things like Hoard with the caveat that
memory passed between threads must always return to the allocator to be
freed.)
What I'm getting at is that a "universal locking mechanism" is not the
solution. Individual structures (e.g. linked lists) need to be treated
separately and used to build up higher lock free (no use of O/S locking
calls) and even wait free structures (e.g. hash table based off those "safe"
linked lists).
For example, such a lock free and wait free linked list can be built by
using the simple atomic add/exchange instructions on Intel chips. This in
itself is orders of magnitude faster than any lock-based system (I'm
thinking Mutex's here as in the Windows API sense) and the Windows API
includes such an implementation already.
However, it is by no means the best solution due to the overhead of the
atomic instructions (not chip specific; all of the multi-CPU/Core hardware
has this behaviour). The best papers out there right now talk about
lock-free/wait-free without relying on (or at least minimising) such
instructions.
The key problem is to have enough understanding of how Judy is implemented
in order to identify the exact areas that have contention under some number
of writers/readers.
Example: if restricted to 1-writer and 1-reader only each on a different
thread running simultaneously on multi-core architecture, what point(s) in a
call to read an existing Judy structure would conflict with a simultaneous
call to write the same structure? Specific lines of code here are needed,
not just "this routine needs to have exclusive access".
As per the comments of the author cited in my previous posting to this
forum, a basic hash table implementation is around 300 lines long whereas
Judy is considerably more.
Whereas the former is well understood and can (via Google and cut 'n' paste)
be transformed into any number of lock free (even possibly wait free and
even atomic instruction free) structures, the latter is far harder due to
the code length and complexity.
A similar effort to what the authors undertook to understand and implement
for a chip feature like cache line size would be required to decompose and
reassembly Judy to take advantages of the new papers in this complex area.
Any takers?
Regards,
Toni.
----
Toni Cassisi
Tovica Ltd
<http://www.tovica.com> http://www.tovica.com
Tel: +44 (0) 7971 874 054
IM: AOL/Yahoo/MSN: tcassisi
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Doug Baskins
Sent: 28 March 2007 05:30
To: Aleksey Cheusov; [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]; [email protected]
Subject: Re: PS about locking Judy arrays
Hi all:
The current version of Judy (1.0.3 I think) uses malloc(3) for
all memory allocation. Malloc(3) in Linux is very little of the
overhead of Judy. The thread safe version of Judy is a high
wish enhancement, but a universal locking mechanism is not
available now (one that is substantially less than the speed of
Judy itself). I hope that Intel designed the Core 2 duo stuff
correctly, but that remains to be explored.
Doug Baskins - author of Judy
Aleksey Cheusov <[EMAIL PROTECTED]> wrote:
...
> You must realize that our small team had our hands full just producing
> Judy IV (the fourth and final version, massive rewrite, the one put on
> SourceForge) before HP cancelled the project. We only scratched the
> surface in several directions, such as shipping Judy with it's own "good
> malloc()" (but then the linking application must use it too),
The right direction is to remove any malloc library from inside Judy.
If you think Judy really needs it and you have idea how to implement it,
IMHO it is MUCH better to open SEPARATE project related only to malloc
and to keep Judy as small as possible. This way is more flexible.
I beleave Judy users know better what kind of malloc should be used.
--
Best regards, Aleksey Cheusov.
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
Doug Baskins <[EMAIL PROTECTED]>
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
