Re: [boost] [intrusive] Looking for some advice on intrusive splaytrees

From: Dave Jenkins (david_at_[hidden])
Date: 2007-10-20 02:26:27

>"Ion Gaztañaga" <igaztanaga_at_[hidden]> wrote in message 
>news:471926A7.3000401_at_gmail.com...
>Dave Jenkins escribió:
>> Rather than remove
>> the self-adjusting optimization, we decided to enable it conditionally
>> when BOOST_DISABLE_THREADS is defined and exclude it otherwise.
>
>Ummm.. IMHO this option is surely safe but many times a library is
>compiled as multithreaded even if only a thread is used.

Defining BOOST_DISABLE_THREADS doesn't prevent you from compiling
multithreaded.  And if it *is* defined, you can safely splay in all cases.

>Apart from
>that, having threading enabled does not mean that containers will be
>shared between threads (we can have a GUI and the backend thread).

That's a good point.  You could use a macro specific to your library
to indicate that it's safe to splay in all cases.  But, if it's only
*sometimes* safe to splay, that won't work.

In that case, my favorite is your idea of default splaying with a thread
safety warning.  And also offering a splay_tree.find(a, dont_splay) for
when you want don't want splaying.

>Sadly, a splay tree that does not splay on searches, is no longer a
>splay tree and will have quite bad performance. You didn't have any
>noticeable performance impact when multithreaded was enabled?

We did see a 10% drop in performance when the self-adjusting optimization
is disabled, for a typical search. Of course, a lot depends on how skewed
the access pattern is.  Our ternary search trie is hidden inside other code,
so it would be difficult to selectively disable/enable.  That's why we went 
for
the "big hammer" of BOOST_DISABLE_THREADS.

Regards,
Dave Jenkins