On Tue, Jan 19, 2021 at 04:46:36PM +0800, Chung-Lin Tang wrote:
> > > + into the (above) structelem_refcount field of the _FIRST
> > > splay_tree_key,
> > > + the first key in the created sequence. All structure element
> > > siblings
> > > + share a single refcount in this manner. Since these two fields
> > > won't be
> > > + used at the same time, they are stashed in a union. */
> > > + uintptr_t *structelem_refcount_ptr;
> > > + };
> > > struct splay_tree_aux *aux;
> > > };
> > > /* The comparison function. */
> >
> > Anyway, most of the patch looks good, but I'd like to understand the
> > rationale for choosing a htab over what I've been trying to suggest, which
> > was essentially instead of incrementing or decrementing refcounts push them
> > into a vector for later incrementing/decrementing, then qsort the vector
> > (by the pointers to refcounts) and increment what the elements point to
> > unless
> > the same address has been incremented/decremented already.
> >
> > Jakub
>
> Essentially the requirement is to increment/decrement a refcount only once
> per construct,
> so using a pointer-set (implemented by htab_t here) to track the processing
> status
> seemed to be more intuitive in code, and probably faster than sorting a
> vector I think
> (at least in most cases).
I agree about the more intuitive, but think it will be actually slower, and
performance is what we care about most here, the mapping is already too
slow.
The common case is only a few mappings and no repeated mappings (e.g. the
compiler ought to help there and just remove mappings that are provably
duplicate if possible). E.g. with one mapping, no qsort is needed at all,
and generally should be O(n log n). The hash set needs larger memory
allocation than the vector and needs it cleared, plus it is a hash table
without chains, so there is some cost on collisions and if ever the hash
table needs to be expanded. But I'll be happy to be proven wrong.
Jakub
