RFA: New V3 demangler

[Ian Lance Taylor]

Daniel Jacobowitz <drow@mvista.com> writes:

> On Thu, Nov 20, 2003 at 04:05:56PM -0500, Ian Lance Taylor wrote:
> > So, I wrote a new V3 demangler in C.
> > 
> > This demangler probably isn't going to win any speed or memory size
> > prizes, but it shouldn't be too bad.  And it does seem to work.
> 
> I'm curious - could you time test-demangle on both demanglers?  The
> demangler showed up as a hotspot in GDB startup times in a conversation
> on gdb@ today.  While the biggest wins are to be had by demangling
> less, a faster demangler would help too.

I ran nm on libstdc++-v3.a, pulled out the symbol name, put them in a
file, and catenated the file together 16 times, to get a 83,392 line
file with mostly one mangled name per line.  I built the binutils
cxxfilt program with both the old libiberty demangler and new
demangler which I just wrote, both compiled with -O2.  I ran the
programs with the file of mangled names as stdin, with stdout directed
to /dev/null.

The output of time for the old demangler was

real	0m1.586s
user	0m1.550s
sys	0m0.040s

The output for the new demangler was

real	0m0.678s
user	0m0.600s
sys	0m0.080s

I ran both programs several time, and although there was some
variances these times are fairly representative.

I also wrote a little C++ test program similar to cxxfilt and linked
it with the C++ demangler.  The I/O was not done the same way, so
these times are not directly comparable.  The results were

real	0m2.342s
user	0m2.280s
sys	0m0.060s

So the new demangler appears to be reasonably faster than the existing
code.  I'm a bit surprised by this, as I don't see any obvious reason
for the old demangler to be slow, and the new one uses a two-pass
algorithm which I would have guessed would be slower.  However, I'm
not interested enough to investigate further.

> Also, I see that DMGL_PARAMS is ignored (I don't know if the old one
> did the same, definitely might).  Is it possible to more efficiently
> demangle just the function name when DMGL_PARAMS is not specified?

The old V3 demangler also ignored DMGL_PARAMS.  It would certainly be
possible to add support for it.  It would be more efficient, since it
would basically mean that the demangler could stop part way through a
mangled function name.  I'll put this on my list.

Ian