Subject: Re: profile results for new UT_* implementations?
From: Dom Lachowicz (dominicl@seas.upenn.edu)
Date: Tue Jun 19 2001 - 22:24:02 CDT
Quoting Paul Rohr <paul@abisource.com>:
> Hi folks,
>
> In wading through the sources today looking at all those leaks, I
> realized
> how substantially the codebase had changed due to the pre-0.9.0
> (re-)implementations of:
>
> strings
> hash tables (now renamed, right?)
> ref-counted objects
>
> It's obviously not time to revisit those design decisions, but I was
> wondering if anyone could point me at the relevant design threads to
> help me
> get up to speed on the rationale behind the new implementations of such
> very
> fundamental data structures.
Hi Paul,
I'd like to address your concerns.
1) Abi never had any string classes (nor anything even remotely resembling
them). The closest thing that we had was either:
a. UT_Bytebuf (ick)
b. Our own management using malloc, free, new, delete, delete[], and all of the
not-so-wonderful inconsistencies that came with them, not to mention keeping
track of everything (size, pointers) and ownership of the strings, since to
this point Abi had no clear ownership model for *any* of its pointers or
references, save the singleton classes
So now we have a nice wrapper class for C strings and UCS2 strings, which is
nice on the eyes, easier on the programmers, and probably more effecient both
in terms of time and space. They support a lot of nice, clean operations,
manage memory for us effectively, etc... We no longer have strcat's in our
code. This is a good thing.
2) The old hashmap was gawd-awful. I did better than that using Pascal in my
high-school CS classes. Jeff's implementation (while ok for a "demo") had no
business being in a release-quality application. It didn't have a clear
ownership policy for keys or values and didn't support something as simple as a
'delete' or 'remove' operation, which was vital for our styles support
2.a) UT_AlphaHash? A strcmp ordered hash-map? WTF? Ordered associative arrays
(maps) are called Vectors or Lists and you can sort them via an insertion sort
if you want too (or quicksort or something at some later time), and do not
support (nor do they need) an associative lookup operator. And the keys are
ordered/saved via a StringPool? k...
3) No classes use reference counting now. UT_AbiObject supports it but no
classes subclass/inherit it (yet? ever?) so this is not an issue.
> In particular, I'd love to see the profile results which showed that
> we've
> gotten better time/space tradeoffs than we had with the older Jeff-style
>
> code I was familiar with. (Or are Martin's view-level rewrites
> responsible
> for all the speedups?)
You don't need better time/space tradeoffs to advocate a change, and even if
these new impls were 3x slower than what we had (which they aren't), I'd still
advocate using them (and optimising them, as well, of course). Before the
changes, we spent an overwhelming majority of our time inside of HashMap
related functions (3 of our top 5 functions, iirc). I haven't pulled out
memprof or gprof lately (which I've been meaning to do) to see how we're doing
now.
> Paul,
> conservative old-timer
Dom
not a masochist
This archive was generated by hypermail 2b25 : Tue Jun 19 2001 - 22:24:25 CDT