headers
Nicolas Neuss | 1 Nov 2004 12:21
Picon

Re: Hash table performance relative to association lists

Hello,

the problem is the same with CMUCL.  Looking at the code there, I see that
GETHASH is not short, not optimized, and has to use WITHOUT-GCING.

Another overhead of hash-tables via lists is that the default size is quite
large (65 for CMUCL, other values can be given, but later in the code a
minimal size of 37 is ensured).  I once tried to change something there,
but my change broke CMUCL and I refrained.

Faster and (by default) smaller hash-tables would be really nice to have in
both SBCL and CMUCL.

Nicolas.

P.S.: Such an improvement might speed up my programs noticeably.
Therefore, I would like to help a little.  If someone manages to improve
this in SBCL/CMUCL significantly (say such that list and hash-table access
are at equal speed for about 10-20 items and that the default size is also
in this range), I would like to offer a Amazon gift certificate of 50 EUR
value.

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 5 comments |
headers
Tony Martinez | 1 Nov 2004 14:44
Picon
Favicon

(patch) Make socket stream names user-overridable

Patchlet which allows the user to specify a name for socket-created
stream.

                                        --Tony

Index: sockets.lisp
===================================================================
RCS file: /cvsroot/sbcl/sbcl/contrib/sb-bsd-sockets/sockets.lisp,v
retrieving revision 1.12
diff -u -r1.12 sockets.lisp
--- sockets.lisp	1 Aug 2004 23:33:06 -0000	1.12
+++ sockets.lisp	1 Nov 2004 11:39:54 -0000
 <at>  <at>  -267,7 +267,7  <at>  <at> 
     (unless stream
       (setf stream (apply #'sb-sys:make-fd-stream
 			  (socket-file-descriptor socket)
-			  :name "a constant string"
+                          :name (or (getf args :name) "a constant string")
 			  args))
       (setf (slot-value socket 'stream) stream)
       (sb-ext:cancel-finalization socket))

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 0 comments |
headers
Nathan Froyd | 1 Nov 2004 18:23

Re: Hash table performance relative to association lists

On Sun, Oct 31, 2004 at 06:00:21PM -0500, Raffael Cavallaro wrote:
> On Oct 30, 2004, at 6:41 PM, Adam Warner wrote: 
> >  I 
> > believe the code below demonstrates that, depending upon the 
> > idiosyncrasies of your hardware, an association list with 40 
> > elements can 
> > be accessed faster than a hash table of those forty elements (both 
> > using 
> > an EQ test). 
> > 
>  
> Using sbcl 0.8.15 on Mac OS X 10.3.5 on a dual G5 machine, the times 
> are almost exactly the same: 

Results for N=40 on my lowly 800MHz Pentium III running Linux 2.4.20
with SBCL 0.8.14.7:

Evaluation took:
                 20.933 seconds of real time
                 18.04 seconds of user run time
                 2.63 seconds of system run time
                 0 page faults and
                 331,809,960 bytes consed.
Evaluation took:
                 19.284 seconds of real time
                 16.29 seconds of user run time
                 2.71 seconds of system run time
                 5 page faults and
                 331,807,512 bytes consed.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Thomas F. Burdick | 2 Nov 2004 02:36
Picon

Re: impending sbcl-0.8.16

Thomas F. Burdick writes:
 > William Harold Newman writes:
 >  > If we don't discover too much exciting emergent behavior in the next
 >  > few days, I'll probably release sbcl-0.8.16 next Sunday or Monday. In
 >  > the meantime, as usual, please avoid excessively exciting innovations
 >  > in the codebase.
 > 
 > Oops, here's an updated patch to fix building on OS X 10.2 that I've
 > been meaning to send in:

Did anyone have any objections to this patch?  If not, uhm, it'd be
nice if 0.8.17 built on 10.2 out of the box.

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 0 comments |
headers
Thomas Schilling | 2 Nov 2004 10:12
Picon
Favicon

Re: Hash table performance relative to association lists

Am Montag 01 November 2004 12:21 schrieb Nicolas Neuss:
> P.S.: Such an improvement might speed up my programs noticeably.
> Therefore, I would like to help a little.  If someone manages to improve
> this in SBCL/CMUCL significantly (say such that list and hash-table access
> are at equal speed for about 10-20 items and that the default size is also
> in this range), I would like to offer a Amazon gift certificate of 50 EUR
> value.

I think you can keep your money ;) I just noticed the following:

  I tested the OP's code on SBCL 0.8.16 and I think we should pay attention to 
the absolute numbers:

  1. the original code is bad for a benchmark since it involved bignums:

CL-USER> (hoo)
Assoc list count check 820000000
Evaluation took:
  		 12.701 seconds of real time
  		 11.64 seconds of user run time
  		 0.949 seconds of system run time
  		 0 page faults and
  		 331,773,864 bytes consed.
                 ^^^^^^^^^^^------- this is bad ---------
Hash table count check 820000000
Evaluation took:
  		 11.158 seconds of real time
  		 10.159 seconds of user run time
  		 0.942 seconds of system run time
  		 0 page faults and
(Continue reading)

Permalink | Reply | 4 comments |
headers
Christophe Rhodes | 2 Nov 2004 13:02
Picon
Picon
Favicon

New toy!

Hi,

sbcl-0.8.16.26, just merged, builds with full 21-bit Unicode support
by default; it is still possible to build a system which resembles
historical versions more closely (only with fewer bugs :-) by removing
:SB-UNICODE in customize-target-features.lisp.

I have only tested this on x86/Linux; it is entirely possible that I
have goofed in merging things (for the PPC) or just implementing them
blind (for the other platforms); I warmly encourage testing of simple
buildability earlier rather than later in the development cycle -- we
still have 18 whole days to go before freezing this month's sbcl, so
there is plenty of time to deal with problem reports as long as we get
them early enough.

There are some known problems.  Firstly, as I mentioned on this list
before (without anyone coming to offer a strong opinion, as I recall)
the sb-md5 contrib fails its tests.  The problem lies in the
MD5SUM-SEQUENCE function operating on a string: there is an underlying
assumption that the character sequence in memory has an identical
octet layout as the same sequence of characters in a file; this
assumption does not hold with :SB-UNICODE enabled.  (And indeed it
doesn't even hold in the old world for high-bit characters, which are
typically encoded in utf-8 on disk but in latin1 in memory.)  It is
likely that there is third-party software (such as SB-SHA1, Blowfish
and the like) which is similarly afflicted by this change.

Secondly, there are performance implications in all these changes.
Nothing should be too drastically pessimized, but if there is
something which has degraded performance it would be good to know
(Continue reading)

Permalink | Reply | 8 comments |
headers
Nicolas Neuss | 2 Nov 2004 13:48
Picon

Re: Hash table performance relative to association lists

Thomas Schilling <tjs_ng <at> yahoo.de> writes:

> I think you can keep your money ;) I just noticed the following:

What a pity:-) I had hoped to have a large speedup for little money...

>   1. the original code is bad for a benchmark since it involved bignums:
> ...
>   2. so I used half the original number of repitions:

You're right, this requires a better benchmark.  On my machine the list is
still two times faster, though.

Hmm, probably it will not be easy to speed up SBCL or CMUCL in such a
fundamental functionality as hash tables.  Somehow this was to be
expected...

Nicolas.

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 3 comments |
headers
Nikodemus Siivola | 2 Nov 2004 14:31
Picon
Picon

Re: Hash table performance relative to association lists

On Tue, 2 Nov 2004, Nicolas Neuss wrote:

> Hmm, probably it will not be easy to speed up SBCL or CMUCL in such a
> fundamental functionality as hash tables.  Somehow this was to be
> expected...

One idea I that might or might not work is making EQ, EQL, EQUAL,
EQUALP, and user-specified hashtables all distinct structure-classes,
so that under right circumstances type-inference would allow inlining
comparison and hash-functions. This would probably pay off better if
support was added for type declarations of the form (hashtable
<hashtype>), though... blech.

Just thinking out loud,

  -- Nikodemus              Schemer: "Buddha is small, clean, and serious."
                   Lispnik: "Buddha is big, has hairy armpits, and laughs."

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 2 comments |
headers
Ingvar | 2 Nov 2004 15:44
Picon

Re: Hash table performance relative to association lists

Nikodemus Siivola writes:
> On Tue, 2 Nov 2004, Nicolas Neuss wrote:
> 
> > Hmm, probably it will not be easy to speed up SBCL or CMUCL in such a
> > fundamental functionality as hash tables.  Somehow this was to be
> > expected...
> 
> One idea I that might or might not work is making EQ, EQL, EQUAL,
> EQUALP, and user-specified hashtables all distinct structure-classes,
> so that under right circumstances type-inference would allow inlining
> comparison and hash-functions. This would probably pay off better if
> support was added for type declarations of the form (hashtable
> <hashtype>), though... blech.
> 
> Just thinking out loud,

In theory, the generic hash table code I cobbled together recently (need
to make a new release, there's some new goodies) is written so that one can, 
in *theory* at least, create new subclasses of GENERIC-HASHTABLE and then
hope that CLOS is good-enough to pick up on the relevant method.

However, as the code is written... hang on, that is probably the issue, actual 
equality function and hash-generator are grabbed once per set and once per 
read from the hash-table.

//ingvar

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
(Continue reading)

Permalink | Reply | 0 comments |
headers
Alexey Dejneka | 3 Nov 2004 04:24
X-Face
Picon
Favicon

PRINT-CLOOP is not implemented

Hello,

From src/compiler/vop.lisp:

  (defstruct (cloop (:print-function print-cloop)

But PRINT-CLOOP does not seem to be defined. So DESCRIBing/INSPECTing
of blocks causes an "undefined function" error.

--

-- 
Regards,
Alexey Dejneka

"Alas, the spheres of truth are less transparent than those of
illusion." -- L.E.J. Brouwer

-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
Permalink | Reply | 1 comment |

Gmane