freenode/#sicl - IRC Chatlog
Search
8:32:06
no-defun-allowed
On an SBCL host, I could use SB-KERNEL:GET-LISP-OBJ-ADDRESS to get the representation (not an address per sē for immediate values) of a value and push a function that rehashes all affected hash tables to *AFTER-GC-HOOKS*, but I'm not sure how much effort you think is appropriate with unportable optimisations.
8:33:41
beach
It is up to you if you want your code to work for SBCL. For SICL, the idea is to move keys to the global heap where their addresses will never change.
8:37:34
no-defun-allowed
Another plan at the back of my head is that bucket hash tables with EQ or EQL tests could use the hash as a "first guess", searching the bucket it designates first, then trying the others after. That would usually be faster than using an alist of all the values (provided the hash function is faster than doing however many comparisons, which admittedly is unlikely for EQ or EQL) but still slower than
8:39:41
beach
Do you mean that it would use the address, but that may be wrong if the object has moved?
8:40:07
no-defun-allowed
Then if it's in another bucket, it could be rehashed; but I would have to do a lot of testing because it could also be much slower.
8:40:50
beach
I think you can rely on the system having a way to detect that the GC has been run so that you can rehash then.
8:41:06
no-defun-allowed
It could, but I think it is also possible (but maybe not likely) it could be effective if even SXHASH is used.
8:42:08
beach
I see. I have not given much thought to SXHASH, so I don't think I'll be of much help.
8:46:43
no-defun-allowed
...since, well, I got interested in hash table implementation after reading about other language implementations' hash functions being the same for every table, and thus possible to attack by picking keys which have the same hash (modulo the table size), forcing it to make O(n) lookups.
8:52:54
no-defun-allowed
I have an implementation of the Fowler–Noll–Vo hash function from earlier experiments which can take any random initial state, which could make it difficult to pick adversarial keys. It also is very easy to write as a function which combines a previous state and new data, so it is quite suitable for implementing a SXHASH in my opinion.
8:56:48
beach
I think it would be fantastic if we (i.e. the SICL project) could suggest better hash-table implementations not only for SICL, but for other Common Lisp implementations as well.
9:10:00
no-defun-allowed
Yeah, after that, implementations of some other languages added salts and variance, but I haven't (so far) heard of any Lisp implementations that do.
9:14:37
shka_
hey heisig i implemented closure compilation approach, i don't have benchmarks yet, but code is much cleaner then the old one
9:19:20
no-defun-allowed
Nope, I don't, I made a typo while generating some benign keys to compare timings from.
9:46:36
no-defun-allowed
But something like that should be possible, and it would make for a not uninteresting talk.
10:17:31
no-defun-allowed
By picking fixnums that have the same hash (modulo the size of the table), I can get a very small variance (around 10%), but it could well be experimental error even though I test it a lot of times.
10:19:49
no-defun-allowed
Maybe the trick involves strings or some other composite type instead. Strings are slower to compare, and some web libraries and languages use hash tables to represent request parameters (such as PHP's $_GET).
10:50:09
no-defun-allowed
And I can create a table where all the pairs are in one bucket, but there seems to be no performance degradation.
10:51:49
no-defun-allowed
There is a single cache element to my knowledge, but I try to miss the cache by testing several different keys.
11:05:18
no-defun-allowed
Actually, I can't quite get them all in one bucket, but there is at least significant clustering.
11:16:37
no-defun-allowed
Got it, the bucket position is calculated modulo the index vector's length (which is the power of 2 above the pair vector's length), not the pair vector's length. Now I have all the eggs in one basket, and I can drop it as I please.
11:33:29
no-defun-allowed
Oddly, it appears putting all the string keys into one bucket makes GETHASH 10% or so faster than with them spread out. Maybe if you're kind enough to arrange the keys optimally, the program will get embarrased and will fall over.
14:23:44
beach
pnp: You should do: (asdf:load-system '#:sicl-boot) (in-package #:sicl-boot) and finally (defparameter *b* (boot))
14:24:16
beach
pnp: Some of the new SICL code is incompatible with the Cleavir version 1 systems. The SICL-BOOT system has the right dependencies.
14:26:31
beach
And since it is not really necessary for further development, I have not taken time to fix it.
14:29:43
beach
And I don't know whether any of the environments resulting from bootstrapping could play that role.
14:33:53
beach
Like I said, the REPL isn't that useful to me. So it would be there only to show off.
14:34:52
beach
Well, all the phases are executed by the boot procedure. So then all the environments are as full as they get. And I am thinking none of them is full enough to justify a REPL.
14:35:42
beach
The best thing might be to create a special environment for the REPL, and import lots of stuff from the others, and the rest from the host.
14:36:13
beach
So the REPL itself is not hard to accomplish, but it is tedious to set up an appropriate environment for it.
15:04:39
beach
At some point, I would like to know how to fix that problem, because I can't use McCLIM on my dinky laptop because of the same issue.
15:23:33
beach
There is not much you can do after (defparameter *b* (boot)). You can inspect the environments I guess, starting with the boot object.
15:25:10
beach
As for the difference between Cleavir and Cleavir version 2, most of the code is the same, but some instructions are different, and Cleavir 2 handles the dynamic environment better. I just didn't want to break Clasp by modifying Cleavir in some radical way.
15:28:04
pnp
anyway i am in the package SICL-BOOT (at the end of the boot) and i can't use (clordane:inspect *b*)
15:30:39
pnp
Another error: Socket error in "connect": ECONNREFUSED (No connection could be made because the target machine actively refused it.)
15:33:15
beach
The documentation for McCLIM is not complete. If you need to write a McCLIM application, you need the CLIM II specification. But the documentation gives you Clouseau in chapter 5: metamodular.com/mcclim.pdf
15:37:36
pnp
when you say good luck i perceive that it's like an impossible task. Do you know if it is feasible or not?
15:40:56
beach
Trucler for lexical environments, Eclector is a portable reader, Concrete Syntax Tree handles source tracking.
15:42:03
pnp
ok.. i will do other questions in a different time. I need time to read, keep in mind some concepts and formulate additional questions. Thank you again for your patience and help
19:50:42
no-defun-allowed
pablore: I have a REPL for SICL prepared, but I don't know where it should go in the code directory.