Re: [PATCH] Add ternary search trees to libiberty

[Daniel Berlin <dan at cgsoftware dot com>]

DJ Delorie <dj@redhat.com> writes:

> What I meant was, have you thought of any other projects (gcc,
> binutils, newlib, cygwin) that could use it, and thus is it being
> developed in a project-independent way and does it make sense to
> burden those project with yet more code they won't use?  I don't mind
> adding generic things to libiberty (within reason), as long as they'll
> get used by more than one project.  However, things in libiberty are
> expected to meet higher standards than things private to a single
> project, and if it's only going to be used by one project anyway you
> will be adding some overhead (for yourself and for other projects) if
> you put it in libiberty.

Well, whenever I go to add another generally useful data structure to gdb or gcc, I get
told it should really go in libiberty instead.
For instance, the compressed bitmaps.
I was also planning on trying to start moving some of the useful data
structures (like the other bitmap implementations) that gcc uses into
libiberty.

Libiberty says it's a collection of subroutines used by various gnu
programs.  I'm trying to introduce TST's into various gnu programs (>1), in
approriate places. So I figured it would make more sense to have it in
libiberty.

> 
> > In short, there's a lot of places we could use it besides GDB.
> 
> Examples?  

Anywhere hash tables or balanced trees are used, and the keys are
strings, TST's are probably a better choice.  They are simpler
algorithmically, and perform better.  You also don't run into the
"let's have 80 hash functions scattered about" problem.

They are starting to be used in all sorts of programs for searching
structures. For instance, a random example, tinyproxy, a GPL'd tiny
HTTP proxy uses them.
Of course, it's not a libiberty consumer, but, as I said, i'm
introducing them into various places in other libiberty using GNU
programs.  

> Aside from stringpool (I assume you mean gcc's); I'd be
> interested in seeing benchmarks on that change.  GCC's performance is
> a hot topic these days.
Yup.

> 
> > We have expandable hash tables in libiberty, why not TST's?
> 
> The hash table code is before my time, although they seem to be used
> only by gcc at the moment.

I started replacing some hash tables in gdb with this code (the ones
not string key based), i haven't submitted the patch yet to gdb-patches.

There are also a few places where we could just use sbitmaps instead
of hash tables (IE there's no data, we are just marking stuff).
>   If you search the archive, you'll see that
> I'm pushing back on gcc to reconsider gcc-specific things in libiberty
> also.  And "but X is in there" isn't a valid reason to add something.
> It should have its own justification.

Well, I was curious mainly because I was planning on trying to move
the bitmap structures that are generally useful into libiberty
We currently, in gdb, end up searching the same blocks over and over
again, because we don't mark that we searched them (and we can end up
with blocks that are the children of more than one thing). I had a
patch to keep a small hash of them, but this is overkill. I keep
wanting to just use a single sbitmap, after giving each block a unique
id (easy), and be done with it.
But it's not in libiberty, so it doesn't get done.

-- 
I was going 70 miles an hour and got stopped by a cop who said,
"Do you know the speed limit is 55 miles per hour?"  "Yes,
officer, but I wasn't going to be out that long..."