[Gcl-devel] efficiency of package symbol tables

[Bruno Haible]

Hi,

Sam Steingold and I found a performance problem in clisp, and it appears
that GCL has the same problem: When tens of thousands of symbols are added
to a package, further package lookups and symbol additions become slower
and slower. This is of course not the proper behaviour for good hash tables.

Here is the test code:

(defun random-symbol ()
  (intern (write-to-string (random 1000000000000000000) :base 36)
          *package*))
(compile 'random-symbol)

(defun fill-symtab (n)
  (dotimes (i n) (random-symbol)))
(compile 'fill-symtab)


And here are the timings with gcl-2.5.3:


>(time (fill-symtab 10000))

real time : 0.090 secs
run time  : 0.090 secs
NIL

>(time (fill-symtab 10000))

real time : 0.180 secs
run time  : 0.190 secs
NIL

>(time (fill-symtab 10000))

real time : 0.240 secs
run time  : 0.250 secs
NIL

>(time (fill-symtab 10000))

real time : 0.260 secs
run time  : 0.260 secs
NIL

>(time (fill-symtab 10000))

real time : 0.330 secs
run time  : 0.330 secs
NIL

>(time (fill-symtab 10000))

real time : 0.350 secs
run time  : 0.340 secs
NIL

>(time (fill-symtab 10000))

real time : 0.420 secs
run time  : 0.410 secs
NIL

>(time (fill-symtab 10000))

real time : 0.480 secs
run time  : 0.470 secs
NIL

>(time (fill-symtab 10000))

real time : 0.460 secs
run time  : 0.460 secs
NIL

>(time (fill-symtab 10000))

real time : 0.470 secs
run time  : 0.470 secs
NIL

>(time (fill-symtab 100000))

real time : 8.040 secs
run time  : 7.460 secs
NIL

>(time (fill-symtab 100000))

real time : 11.950 secs
run time  : 11.890 secs
NIL

>(time (fill-symtab 100000))

real time : 15.900 secs
run time  : 15.610 secs
NIL

>(time (fill-symtab 100000))

real time : 19.980 secs
run time  : 19.880 secs
NIL

>(time (fill-symtab 100000))

real time : 24.380 secs
run time  : 24.160 secs
NIL


What helped us in order to understand the problem, was to look at the
internal distribution, how many symbols in each bucket of the hash table
on average...

Regards,

Bruno


PS: Btw, INTERN gives a wrong error message:

(intern "FOO" "CL-USER")

Error: "CL-USER" is not of type (OR SYMBOL STRING ...).
Fast links are on: do (si::use-fast-links nil) for debugging
Error signalled by INTERN.
Broken at INTERN.  Type :H for Help.

What it means to say is that the package CL-USER does not exist...