[Top][All Lists]
[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
|
|
- [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/08
- RE: [Gcl-devel] efficiency of package symbol tables,
Mike Thomas <=
- Re: [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/10
- Re: [Gcl-devel] efficiency of package symbol tables, Camm Maguire, 2004/03/20
- Message not available
- Re: [Gcl-devel] efficiency of package symbol tables, Camm Maguire, 2004/03/21
- Re: [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/21
- Re: [Gcl-devel] efficiency of package symbol tables, Sam Steingold, 2004/03/21
- Re: [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/21
- Re: [Gcl-devel] efficiency of package symbol tables, Camm Maguire, 2004/03/21
- Re: [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/22
- Re: [Gcl-devel] efficiency of package symbol tables, Camm Maguire, 2004/03/22
- Re: [Gcl-devel] efficiency of package symbol tables, Bruno Haible, 2004/03/22