This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] Offloading Support in libgomp

On Sun, Sep 15, 2013 at 07:41:24PM +0400, Michael V. Zolotukhin wrote:
> > Libgomp will start N-1 new threads, and all of them would want to look up
> > mappings for i1,i2,...iK in the splay tree.  The first one wouldn't find
> > anything and would map and insert all the values to the tree.  But the following
> > ones would look-up these addresses in the exactly same order, which will lead to
> > totally unbalanced tree.
> > 
> > Am I missing anything or is it a real problem?
> On second thought, this access order doesn't necessarily mean accessing in
> ascending/descending keys order, so there is no problem here.

Yes, splay tree can get totally unbalanced and you can have a linear lookup
time, the O(log n) lookup time is amortized.  But, if you e.g. really do
lookup sorted keys (which is not given, the compiler puts vars into the
clauses based on the user order or in the order references to those vars are
discovered, plus for array sections pointer kinds which usually have
different addresses go immediately after the data ones), you really can have
one O(n) lookup if you've looked e.g. the highest address last time and now
you're looking up the lowest and the tree is totally unbalanced, but then
won't the following lookups be all O(1), because the keys you are looking up
will be always immediately in the right child?

Anyway, if the splay trees ever cause issues in real-world, it is not hard
to just replace them by something else (R-B trees, AVL trees or similar).


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]