freenode/#sicl - IRC Chatlog
Search
5:59:22
beach
So, here is the (in my opinion sane) idea of Sweden. When you go to the university, you are a young adult. You are adult, so your parents' situation should not influence yours. You are young, so you haven't had time to build a fortune yet.
5:59:33
beach
Therefore, you must get help from the government. The French get it wrong. The income of the parents counts. But, what if you don't want to take your parents' money? What if your parents don't want to give you theirs?
5:59:41
beach
What if you are a foreign student and your parent's income can not be easily established? This forces many students to work half time, thereby taking twice as long to finish their studies, or they get kicked out for taking too long.
5:59:42
beach
So the French complicate the system by giving special treatment to students who have to work. But then, if you are a foreign student, you don't have a work permit, so you work illegally. So then you can't get a letter from your employer that you have a job. So then you study half time, but are treated as full time. So you get kicked out.
6:05:49
beach
I started my PhD when I was 28, and that was a great advantage. I then had 3 years of industry experience, and I had done my military service.
6:08:28
no-defun-allowed
The "optimum" is that age here, because your parents get upset with you if you take a break (a "gap year" or similar), and 2020 was a pretty bad choice for taking a holiday year.
6:09:38
beach
I suspect that, when I was that age, in Sweden, we were more independent of our parents than most people the same age in other countries and in other periods in time.
6:10:59
splittist
We used to giggle at the Mature Students (as they were called) bringing their life experience to bear in discussions about things like 'justice' and 'power' when the important thing was to "engage with" (i.e. regurgitate the teacher's preferred interpretations of) the Source Material.
6:12:27
no-defun-allowed
Well, we get loans for the other $6,000/year, which have an interest rate that matches inflation. And you only pay it off when you start working, so it could be worse.
6:13:18
splittist
When my father went to law school you were still expected to wear a jacket and tie to lectures. But then, you were also working part-time as a law clerk, so the spirit of '68 was probably of little interest.
6:13:55
splittist
I guess that left the university free to teach the important stuff (what is justice) rather than the operational stuff (how to be a lawyer).
6:14:05
no-defun-allowed
And we're then paid around $250/fortnight if financially dependent, and some more if independent. But for "reasons" I may remain dependent for a while, so I do sometimes have to give a rat's ass about my parents' boring thoughts.
6:14:25
splittist
How industry has sucked the world into thinking 'society' should pay for training their workers astonishes me.
6:15:29
beach
So the French got that aspect right. We have no pressure whatsoever to teach what industry wants.
6:17:36
beach
That, I think is sane. We try to teach stuff that will make society as a whole more productive (i.e., waste less energy, fewer resources, etc.) over time.
6:18:23
beach
But, of course, given the incompetence of most university teachers, that goal is hard to achieve. It is easy for an ignorant individual teacher to look to industry for ideas.
6:19:47
beach
But I can assure you that, when I was in charge of the undergraduate program, that was what we did.
6:22:38
beach
When that was the case, I could speak with some authority, since I was one of the few people with experience from four countries on three continents.
6:23:31
beach
... and experience from both academia and industry, both as a developer and as a manager.
7:47:54
no-defun-allowed
Vaguely good news: I converted the linear probing hash table to use DEFSTRUCT, and it currently is around twice as slow as the SBCL hash table with hits, and about 20% faster with misses.
9:39:59
no-defun-allowed
If I inline the hash function (SB-IMPL::EQL-HASH), as SBCL does, then it approaches only a 50% slowdown for hits, taking 6 nanoseconds compared to SBCL's 4.
9:41:11
no-defun-allowed
It's more "attempting to cheat in the same ways SBCL cheats" than progress, but sure.
9:56:57
no-defun-allowed
Well shit, you had a point about caching the last position, though that might be too useful for a micro-benchmark which repeatedly retrieves one key.
9:57:48
no-defun-allowed
A test at the REPL suggests hitting the cache takes around 2.7 nanoseconds.
9:59:46
no-defun-allowed
Yes, though I can't reproduce it in my program I use to generate the data for those performance graphs.
10:01:09
beach
How much would it show up in a benchmark that always does gethash then (setf gethash) of the same key? That is on common pattern.
10:02:24
no-defun-allowed
What I mean is that, should I type (the-cost-of-nothing:bench (gethash 3 *table*)), it's clearly hitting the cache, and it reports less than 3 nanoseconds. My program which repeatedly does that for different table sizes, however, does not report similar results.
10:03:43
beach
Sure, but those are both extremes. The interesting use pattern is when the key is used exactly twice.
10:08:17
no-defun-allowed
Here a twister comes: my probing code is broken, and overwrites mappings, so GETHASH falls back to normal probing. Not sure how I didn't notice that earlier.
10:08:37
scymtym
no-defun-allowed: i don't know what the surrounding benchmark code looks like, but replacing a special variable access (i suppose *TABLE* is that) with a lexical variable access can have a noticeable impact in tight loops
10:11:56
no-defun-allowed
Ah, the algorithm I used to map over matching elements (using the BSF instruction, which finds the position of the least significant 1 bit) is broken when the least significant bit is zero. Fun.
10:22:17
no-defun-allowed
One sort of strange thing is that (bsf 0) is undefined behaviour, and doesn't signal a fault of any kind.
10:27:03
no-defun-allowed
After fixing that, another problem is apparent: SB-IMPL::EQL-HASH for a fixnum is the identity function, and that's bad news for this hash table. Recall it only picks a group from the top 56 bits, so there will be 256 fixnums mapped to one group of 16 elements (when testing with consecutive fixnums).
10:44:12
no-defun-allowed
I could pick any of the bits, sure. But it's not a problem with the SICL hash functions.
10:49:41
no-defun-allowed
The problem is that the identity function is not a good hash function for ranges of integers with this table, which Kulukundis mentions in his presentation.
10:50:30
beach
I must conclude that the SICL hash function for integers is not the identity function, yes?
10:50:56
no-defun-allowed
However, he says it's only a problem when the low eight bits are the same (like (loop for n below X collect (ash n 10))), when there would still be collisions for (loop for n below X collect n).
10:52:32
no-defun-allowed
After fixing everything, my table is somehow 400 picoseconds faster (on average of a lot of samples and sizes) at reading the cache than the table in SBCL.
11:01:38
no-defun-allowed
Yes, also that the difference is pretty close to one cycle. Is that even significant? It could be the other way around on another machine.
11:22:49
no-defun-allowed
Still, caching like that could get messy in a concurrent hash table, so faster probing would be more significant.
11:55:49
no-defun-allowed
On the other hand, there is a lot of improvement to be made with inserting mappings. Maybe I should just include the SICL hash functions in my "standalone" implementation, since the table is picky about hash functions.