From: Nikodemus S. <nik...@ra...> - 2009-01-18 12:13:52
Attachments:
0001-SB-EXT-DEFINE-HASH-TABLE-TEST.patch
|
The attached patch provides my first on SB-EXT:DEFINE-HASH-TABLE-TEST: SB-EXT:DEFINE-HASH-TABLE-TEST * Based on old SB-INT:DEFINE-HASH-TABLE-TEST, but: ** Macro, not a function. ** Arguments are symbols or lambda forms. ** :TEST accepts only 'NAME, not #'TEST as well. ** Pick up redefinitions of the test and hash-function without re-executing the D-H-T-T form. * Documentation -- other hash-table extensions as well. Cheers, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2009-01-18 14:09:27
|
"Nikodemus Siivola" <nik...@ra...> writes: > The attached patch provides my first on SB-EXT:DEFINE-HASH-TABLE-TEST: The interface that (as I understand it) is provided by Allegro might be worth a look. There, if I remember correctly, instead of having a name for a test/hash-value pair, there's an extra keyword argument to make-hash-table. This is more flexible but maybe also more error-prone? I vaguely wonder about having define-hash-table-test define functions named like (hash-table-test <identifier>) and (hash-table-hash <identifier>), so that the Allegro interface can be easily supported while still also allowing easy defaulting based on a define-hash-table-test name. Sunday afternoon witterings from me, Best, Christophe |
From: Tobias C. R. <tc...@fr...> - 2009-01-18 15:08:45
|
"Nikodemus Siivola" <nik...@ra...> writes: > +(defun register-hash-table-test (name test-function hash-function) > + (declare (symbol name)) > + (tagbody > + :retry > + (let* ((old *user-hash-table-tests*) > + (spec (assoc name old))) > + (cond (spec > + (style-warn "Redefining hash table test ~S." name) > + (setf (cdr spec) (list test-function hash-function))) Is this thread-safe? If not, deliberatively so? > + (t > + (let ((new (cons (list name test-function hash-function) old))) > + (unless (eq old (compare-and-swap (symbol-value '*user-hash-table-tests*) > + old new)) > + (go :retry))))))) > name) > + > +(defmacro define-hash-table-test (name test hash) > + #!+sb-doc > + "Defines NAME as a new kind of hash table test for use with the :TEST > +argument to MAKE-HASH-TABLE. > + > +TEST must name a two argument equivalence predicate, or be a LAMBDA form > +implementing one in the current lexical environment. > + > +HASH must name a hash function consistent with TEST, or be a LAMBDA form > +implementing one in the current lexical environment. The hash function must > +compute the same hash code for any two objects for which TEST returns true, > +and subsequent calls with already hashed objects must always return the same > +hash code. Looking at the implementation, even if the TEST or HASH argument is a symbol, its value is retrieved from the current lexical environment, i.e. (flet ((my-test (x y) ...) (my-sxhash (x) ...)) (define-hash-table-test my-hash-table-test my-test my-sxhash)) does work. I think the documentation should say so; my attempt: Scratch the "in the current-lexical-environment" in both paragraphs, then add a new paragraph which says: The functional values of the TEST and HASH arguments are retrieved from the current lexical environment. I like Christophe's suggestion for a new sub-namespace. -T. |
From: Paul K. <pk...@gm...> - 2009-01-18 15:12:23
|
On 18-Jan-09, at 10:08 AM, Tobias C. Rittweiler wrote: > "Nikodemus Siivola" <nik...@ra...> writes: > >> +(defun register-hash-table-test (name test-function hash-function) >> + (declare (symbol name)) >> + (tagbody >> + :retry >> + (let* ((old *user-hash-table-tests*) >> + (spec (assoc name old))) >> + (cond (spec >> + (style-warn "Redefining hash table test ~S." name) >> + (setf (cdr spec) (list test-function hash-function))) > > Is this thread-safe? If not, deliberatively so? We assume in a dozen other places that (aligned) word-sized stores are atomic. Paul Khuong |
From: Leslie P. P. <sk...@vi...> - 2009-01-18 16:35:18
|
> We assume in a dozen other places that (aligned) word-sized stores are > atomic. Why is this reasonable to assume? -- LinkedIn Profile: http://www.linkedin.com/in/polzer Xing Profile: https://www.xing.com/profile/LeslieP_Polzer Blog: http://blog.viridian-project.de/ |
From: Nikodemus S. <nik...@ra...> - 2009-01-19 06:22:11
|
On Sun, Jan 18, 2009 at 6:35 PM, Leslie P. Polzer <sk...@vi...> wrote: > >> We assume in a dozen other places that (aligned) word-sized stores are >> atomic. > > Why is this reasonable to assume? Atomic in the sense that there is never a "partial" word written anywhere. This is a fact of life on Intel architectures at least (which is the extent of our threaded support so far), and I would assume on pretty much every other platform out there as well. A store like this need not be atomic in the sense of "all threads see it at the same time". Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2009-05-17 20:31:38
Attachments:
0001-SB-EXT-DEFINE-HASH-TABLE-TEST--2.patch
|
2009/1/18 Nikodemus Siivola <nik...@ra...>: > The attached patch provides my first on SB-EXT:DEFINE-HASH-TABLE-TEST: Second cut. I simplified the API to (define-hash-table-test = (lambda (x) (coerce x 'double-float))) ...which is to say NAME has to name the global function to be used as the test function. HASH-FUNCTION must either be the name a global function or a lambda form (which gets evaluated in the current lexical environment.) Both :TEST #'NAME and 'NAME work, and HASH-TABLE-TEST returns 'NAME in either case. Redefinitions of both NAME and global HASH-FUNCTION will be automatically picked up. Package locks protect locked packages -- preventing eg. to well meaning libraries from defining mutually incompatible meanings for :TEST '=. Supporting a :HASH-FUNCTION argument for MAKE-HASH-TABLE test is also possible, but not as nice, I feel: it's never going to play as well with HASH-TABLE-TEST, and makes usage more error prone, requiring getting two connected pieces right every time you want to make a hash table, as opposed to defining the connection for once and for all. Cheers, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2009-05-17 20:47:47
|
Nikodemus Siivola <nik...@ra...> writes: > Supporting a :HASH-FUNCTION argument for MAKE-HASH-TABLE test is also > possible, but not as nice, I feel: it's never going to play as well > with HASH-TABLE-TEST, and makes usage more error prone, requiring > getting two connected pieces right every time you want to make a hash > table, as opposed to defining the connection for once and for all. I haven't been following this discussion, but I'm afraid I think this is exactly backwards, and I don't think there is a "once and for all". I don't see why, even within a single application (because your example using '= clearly falls foul of the locked packages), a single hash function need suit all uses of a single equality predicate; particular hash tables might be used with sufficiently different distributions of keys that distinct hashing functions would be a win. More generally, I can implement your scheme (coupled equality/hash) on top of independent equality and hash functions transparently and with ease. The reverse, while possible is going to be terribly icky: defining a new synonym for an equality function to get hold of a new hash. I wouldn't mind an uncoupled scheme with a default for a given equality, though. Would that be sufficiently easy to use for you while remaining sufficiently general for me? Best, Christophe |
From: Nikodemus S. <nik...@ra...> - 2009-05-19 10:30:00
Attachments:
0001-SB-EXT-DEFINE-HASH-TABLE-TEST-3.patch
|
2009/5/17 Christophe Rhodes <cs...@ca...>: > More generally, I can implement your scheme (coupled equality/hash) on > top of independent equality and hash functions transparently and with > ease. The reverse, while possible is going to be terribly icky: > defining a new synonym for an equality function to get hold of a new > hash. > > I wouldn't mind an uncoupled scheme with a default for a given > equality, though. Would that be sufficiently easy to use for you > while remaining sufficiently general for me? Something like the attached, maybe? Relevant docstring bits below for convenience. from MAKE-HASH-TABLE: :TEST Determines how keys are compared. Must a designator for one of the standard hash table tests, or a hash table test defined using SB-EXT:DEFINE-HASH-TABLE-TEST. Additionally, when an explicit HASH-FUNCTION is provided (see below), any two argument equivalence predicate can be used as the TEST. ... :HASH-FUNCTION If NIL (the default), a hash function based on the TEST argument is used, which then must be one of the standardized hash table test functions, or one for which a default hash function has been defined using SB-EXT:DEFINE-HASH-TABLE-TEST. If HASH-FUNCTION is specified, the TEST argument can be any two argument predicate consistent with it. The HASH-FUNCTION is expected to return a non-negative fixnum hash code. from DEFINE-HASH-TABLE-TEST Defines NAME as a new kind of hash table test for use with the :TEST argument to MAKE-HASH-TABLE, and associates a default HASH-FUNCTION with it. NAME must be a symbol naming a global two argument equivalence predicate. Afterwards both 'NAME and #'NAME can be used with :TEST argument. In both cases HASH-TABLE-TEST will return the symbol NAME. HASH-FUNCTION must be a symbol naming a global hash function consistent with the predicate, or be a LAMBDA form implementing one in the current lexical environment. The hash function must compute the same hash code for any two objects for which NAME returns true, and subsequent calls with already hashed objects must always return the same hash code. Note: The :HASH-FUNCTION keyword argument to MAKE-HASH-TABLE can be used to override the specified default hash-function. Attempting to define NAME in a locked package as hash-table test causes a package lock violation. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2009-05-21 10:28:50
|
2009/5/19 Nikodemus Siivola <nik...@ra...>: > Something like the attached, maybe? Relevant docstring bits below for > convenience. Merged as 1.0.28.63. Cheers, -- Nikodemus |