From: Vladimir T. <vtz...@gm...> - 2008-11-15 09:47:06
|
---------- Forwarded message ---------- From: Vladimir Tzankov <vtz...@gm...> Date: Sat, 15 Nov 2008 11:21:02 +0200 Subject: Re: circularity detection on 64bit platforms with bitmaps To: Don Cohen <don...@is...> Hi, On Nov 15, 2008, at 1:53 AM, Don Cohen wrote: > Vladimir Tzankov writes: >> Just committed (threads1 branch) spvw_circ.d which implements >> circularity detection with LISP hash table (used as hashset). >> The hash table is :fasthash-eq (but there is no big difference in >> performance if :stablehash-eq is used instead). >> >> The overall performance is much worse than with MLB (bitmaps) or gc >> marks. >> On overall I see it about 40-50% slower when running 'make check- >> tests' (on 32 bit). > Can we get some numbers? > What size inputs took how long in each case? These are observations from performing all tests. No special benchmarks are done. will check soon. > Am I correct that this function is only needed when you do PRINT with > *print-circle* true? How does the circle detection compare with the > rest of PRINT? (It slows down PRINT by what %?) It is used when *print-circle* or *print-readably* are non NIL. >> "Easily" can be added more hashset options. The most important >> feature of each implementation is whether it may GC. > I don't understand that sentence. Explain? > Lisp doesn't have hashsets (as distinct from hash tables), does it? > I don't see how a hashtable could always avoid gc when you add to it. The implementation of circularity detection uses a hashset. There are currently two implementations: MLB and via lisp hash table. MLB one - does not cause GC to run, and the lisp hash table cannot always avoid GC. This leads to some differences in the circ detection implementation and is controlled by two macros (all these are implementation details). Easily can be added other hashset implementations - without modifying the circ detection - just care should be taken depending whether it may (not) GC. >> btw: DEBUG_GCSAFETY does not work with GENERATIONAL_GC (at least in >> MT build). Not that I need it - but have tried it while testing. > What's this supposed to do? > I'm guessing reduce the chance of gc errors going undetected. Yes: http://clisp.org/impnotes/gc-safety.html Vladimir |