This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFC] Offloading Support in libgomp
- From: Jakub Jelinek <jakub at redhat dot com>
- To: "Michael V. Zolotukhin" <michael dot v dot zolotukhin at gmail dot com>
- Cc: Marek Polacek <polacek at redhat dot com>, Kirill Yukhin <kirill dot yukhin at gmail dot com>, Richard Henderson <rth at redhat dot com>, gcc-patches at gcc dot gnu dot org, triegel at redhat dot com
- Date: Mon, 16 Sep 2013 08:44:44 +0200
- Subject: Re: [RFC] Offloading Support in libgomp
- Authentication-results: sourceware.org; auth=none
- References: <20130910153810 dot GC2059 at msticlxl57 dot ims dot intel dot com> <20130913112930 dot GC30181 at msticlxl57 dot ims dot intel dot com> <20130913123614 dot GB1817 at tucnak dot redhat dot com> <20130913131109 dot GD30181 at msticlxl57 dot ims dot intel dot com> <20130913131556 dot GD1817 at tucnak dot redhat dot com> <20130913153527 dot GH1817 at tucnak dot redhat dot com> <20130913154103 dot GT23899 at redhat dot com> <20130914192956 dot GI1817 at tucnak dot redhat dot com> <20130915093007 dot GA60139 at msticlxl57 dot ims dot intel dot com> <20130915154124 dot GB60139 at msticlxl57 dot ims dot intel dot com>
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
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).
Jakub