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

> 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?
If the first time the lookup was in increasing keys order, and then we are
looking up in decreasing keys order, then yes, there is no problem and at the
beginning the element we are looking for would be very close to root, so it
would be fast (at the end I guess there would be still O(log N)).  The problem
would be if the order of the 2nd lookup is the same as the order of the 1st

> 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).
Yes, agreed.

> 	Jakub

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