Search
Tuesday, 19th of June 2018, 17:10:59 UTC
17:16:37
pkhuong
if anything, EQL hash tables will be faster than EQ
17:17:27
stassats
eql-hash is slightly suboptimal in its type tests, fixing it right now
17:20:30
stassats
eq => 0.450 sec / 20000000 probes, eql => 0.639, my fixed eql => 0.568
17:28:53
stassats
can make eq-hash better too
17:50:53
stassats
SB-KERNEL:POINTER-HASH claims to "shift the whole address into a positive fixnum.", yet it does (inst shr res 1)
17:51:27
stassats
which would have been true for 3-bit fixnum tags
17:52:10
stassats
i wonder what would be the effect if i fix it, would actually improve or worsen collisions
18:04:19
stassats
the other reason EQL-hash is slower is because #'EQL is slower
18:05:46
stassats
now i want a non-argument-checking-non-rbp-pushing EQ function
18:11:42
pkhuong
last time I looked at our weak eql hash function
18:12:05
pkhuong
it was designed that way for small integers :/
18:12:41
stassats
way way small integers return 0
18:14:32
stassats
that too is due to 1-bit fixnums
18:17:05
stassats
x86: (loop for i to 16 collect (sb-impl::index-for-hashing (sb-impl::eq-hash i) 16)) => (7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0)
18:17:10
stassats
x86-64: (7 7 7 7 7 7 7 7 3 3 3 3 3 3 3 3 0)
18:38:11
stassats
doing (inst shr res 1) (inst and res (lognot n-fixnum-tag-bits)) => (8 8 7 7 6 6 5 5 4 4 3 3 2 2 2 2)
19:31:37
stassats
(inst and res (constantize (dpb -1 (byte (- n-word-bits n-fixnum-tag-bits 1) n-fixnum-tag-bits) 0))) =>
19:31:42
stassats
(7 6 5 4 3 2 1 0 0 15 14 13 12 11 10 9)
19:45:43
corci
Project sbcl-master-windows build #2716: FAILURE in 35 min: http://ci.cor-lab.de/job/sbcl-master-windows/2716/
20:23:30
corci
Project sbcl-master-windows build #2717: FIXED in 37 min: http://ci.cor-lab.de/job/sbcl-master-windows/2717/
1:54:32
pfdietz_
I wonder if fibonacci hashing could help with that https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
1:56:53
aeth
The HN comments seem pretty negative. https://news.ycombinator.com/item?id=17328756
3:13:13
pkhuong
pfdietz_: preferable to have a decent hash function
Wednesday, 20th of June 2018, 5:10:59 UTC