gcl-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Gcl-devel] efficiency of package symbol tables


From: Mike Thomas
Subject: RE: [Gcl-devel] efficiency of package symbol tables
Date: Mon, 8 Mar 2004 16:22:59 +1000

Hi Bruno and Sam.

| 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:
|

Thanks for reporting those two problems.

I tried duplicating the symbol table problem on a Windows XP box with a
pre-release of the ANSI GCL 2.6.2 but could not get that explosion in time
you report after more than 30 iterations, as shown below.

Whether this is because of a change in the nature of the package functions
since 2.5.3 (you seem to be using a CLtL1 build) or because the memory/GC
parameters have been changed since then I can't say.  It will be interesting
to see what Camm gets on Linux.


| 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...


I get similar results as you and will put that in our bug registry:

===========================================================
>(intern "FOO" "CL-USER11")

Error in INTERN [or a callee]: "CL-USER11" is not of type (OR SYMBOL
                                                           STRING
                                                           PACKAGE).

Fast links are on: do (use-fast-links nil) for debugging
Broken at INTERN.  Type :H for Help.
 1 (Abort) Return to top level.
dbl:>>1
===========================================================

Cheers

Mike Thomas.




===========================================================

Exercising package stuff on WIndows.
===========================================================

GCL (GNU Common Lisp)  2.6.1 ANSI   Mar  8 2004 12:29:18
Source License: LGPL(gcl,gmp), GPL(unexec,bfd)
Binary License:  GPL due to GPL'ed components: (UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.

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

RANDOM-SYMBOL

>(compile 'random-symbol)

Compiling gazonk0.lsp.
End of Pass 1.
End of Pass 2.
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling gazonk0.lsp.
Loading gazonk0.o
start address -T 1033f8b8 Finished loading gazonk0.o
#<compiled-function RANDOM-SYMBOL>

>
(defun fill-symtab (n)
  (dotimes (i n) (random-symbol)))

FILL-SYMTAB

>(compile 'fill-symtab)

Compiling gazonk0.lsp.
End of Pass 1.
End of Pass 2.
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling gazonk0.lsp.
Loading gazonk0.o
start address -T 1033fa18 Finished loading gazonk0.o
#<compiled-function FILL-SYMTAB>

>(time (fill-symtab 10000))

real time : 0.367 secs
run time  : 0.367 secs
NIL

>(time (fill-symtab 10000))

real time : 0.417 secs
run time  : 0.417 secs
NIL

>(time (fill-symtab 10000))

real time : 0.417 secs
run time  : 0.417 secs
NIL

.... Delete up to 30th iteration ....

>
(time (fill-symtab 10000))

real time : 2.367 secs
run time  : 2.367 secs
NIL

>(time (fill-symtab 10000))

real time : 2.233 secs
run time  : 2.233 secs
NIL

>(time (fill-symtab 10000))

real time : 2.467 secs
run time  : 2.467 secs
NIL

>


| -----Original Message-----
| From: address@hidden
| [mailto:address@hidden
| Behalf Of Bruno Haible
| Sent: Friday, 5 March 2004 7:05 AM
| To: address@hidden
| Cc: address@hidden
| Subject: [Gcl-devel] efficiency of package symbol tables
|
|
| 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...
|
|
|
| _______________________________________________
| Gcl-devel mailing list
| address@hidden
| http://mail.gnu.org/mailman/listinfo/gcl-devel
|
|






reply via email to

[Prev in Thread] Current Thread [Next in Thread]