#13 Make thread-safe

open
nobody
None
5
2005-10-21
2005-10-21
Anonymous
No

I think quite a few people want to see Judy made
thread-safe. Ideally, this wouldn't be coarse locking,
but rather some mixture of techniques to minimize the
locking actually required. For example, you can often
get away with locking just writers and not readers.

Add in pluggable memory management and an easy way to
serialize the structure to make it persistent and/or
send it over networks, and you'd have the most flexible
data structure around.

The problem with a data structure you can use for
everything though is that it would be really tempting
to have more and more data stored in a tree of Judy
structures, but if you have to lock the whole thing for
every read, then the performance would be WORSE with
threads than without and multithreaded programs are
quite popular!

-- Evan
evan@coolrunningconcepts.com

Discussion

  • S. Nikolov
    S. Nikolov
    2006-05-05

    Logged In: YES
    user_id=1253319

    Frogive me for butting in (I am not affiliated with Judy).
    You can't get away with locking just writers, you know why?
    This is how RW locks work: imagine you have 10 readers
    concurently accessing a data struct and no preexisting
    writers (the reference count in the lock is 10, writer bit
    is off); now a writer comes along - it sets the writer bit
    to on and blocks until all 10 readers have finished; any new
    readers that attempt to grab the lock would be blocked
    meanwhile because the writer bit is set. You can think of
    the lock as a long variable where say 20 bit are used for
    ref. counting, 1 bit for r/w indication and the remaining
    ones for other purposes. Last clue, you can atomically turn
    any bit pattern into any other bit pattern, that's key to
    how rw locks are implemented.

    I just showed you that readers can block as much as writers
    can. On the subject of adding thread safety to judy, I'd say
    sure why not if it doesn't bind me to a particular API such
    as win32 or pthread mutexes. If I want to use judy inside an
    OS kernel then no particular implementation of locks can be
    assumed.