libera/#commonlisp - IRC Chatlog
Search
7:48:05
White_Flame
an implementation can literally store things however it feels like. but there's certain things that are advantageous on common processor designs
7:48:51
White_Flame
tag for "this is a pointer to a cons cell", "this is a pointer to a string", etc
7:50:23
White_Flame
if it knows that it's a cons cell, it can dereference it with a -7 offset to directly hit the cons cell storage without having to mask off the tag bits
7:50:59
bitblit1
White_Flame: Wait, so by this you mean that the value pointing to it would be stored AT 0x1007??
7:52:33
White_Flame
the value at 0x1008 as the cdr could contain the raw machine value 0x1017, which references the next cons cell at 0x1010
7:53:08
White_Flame
or it coud be 0x001f, which let's say 0xf is the tag fro a fixnum, and that's the value 1
7:53:56
bitblit1
White_Flame: Wait, so when you say references AT, you mean it points to right? Not like it is STORED AT?
7:56:02
White_Flame
so we read 0x1000, which is the raw value 0x001f, which is the literal value 1 (fixnum tag 0xf)
7:56:56
White_Flame
so those 4 bytes represent (1 2), and any slot holding the raw machine word 0x1007 is a reference to that list
7:59:10
aeth
in CL, the type tag is basically just achieved with ASH to shift in both directions. One direction removes the tag and gets the data (which is why in SBCL if you disassemble a function with the constant value 1 it shows up as 2, and with 2 it shows up as 4, etc.)
8:01:05
aeth
I'm just guessing that one of the directions would be something like (using the 7 tag) this: (format t "#x~X" (logior (ash 1000 1) #x7)) => #x7D7
8:02:42
beach
An object can be allocated on the stack if that turns out to be safe to do, and slots in objects allocated on the heap will contain tagged pointers.
8:07:31
aeth
but e.g. (format t "#x~X" (logior (ash 1000 8) #x7)) and then reverse it with (format t "~D" (ash #x3e807 -8)) to get 1000 back.
8:07:56
aeth
you can make a list contiguous with CDR coding but modern implementations don't think that it's a worthwhile optimization https://en.wikipedia.org/wiki/CDR_coding
8:08:21
White_Flame
garbage collectors probably also end up reordering lists in car cdr car cdr car cdr order
8:09:58
bitblit1
Wait at the beginning? Why is it O(n)? itn't it like the first object pointed by memory
8:10:58
bitblit1
but a chain of cons cells where each cell consists of 2 words where 1 word is the car and value and the 2nd word is the pointer to the next cell or nil.
8:11:45
beach
bitblit1: You might get some help here: http://metamodular.com/Common-Lisp/Tutorial/semantics.html
8:12:28
aeth
(if foo x y) is probably (if (eql foo nil) y x) at the low level. At least, that's the most obvious way if NIL isn't 0 in the lowest level representation
8:13:53
White_Flame
remember, NIL is a symbol and obeys the cons cell interface, eg (car nil) => nil, (cdr nil) => nil
8:14:56
bitblit1
so a boolean tag would be just a bit but takes but the rest of the three bits (I still don't get why it's not 4) and so it's just a bit where 0x0 = NIL and 0x1 = T
8:18:39
White_Flame
if you only have 3 or 4 bits of tag, then one bit that's a massive percentage of that limited space
8:24:19
beach
bitblit1: In chapter 16 of http://metamodular.com/SICL/sicl-specification.pdf you can see how we do it in SICL.
11:48:09
beach
bitblit1: So if you had a quick look at chapter 16 as I suggested, you will see that only a few types are encoded in the tag bits, and that one of those types is STANDARD-OBJECT where the class of the object is found in a slot in the standard object.
12:09:31
bitblit1
beach: but where is the class of the object and where are slots stored in memory? as its not in the tag bits from my understanding
12:15:21
beach
For that type, when you mask out the tag bits, you have a pointer to memory where the standard object is stored.
12:16:36
beach
And in this case, the standard object is represented in two parts, a "header" that has a slot pointing to the class object, and another slot pointing to the "rack" which is another heap-allocated structure where the slots of the object are stored.
13:16:55
hayley
It's possible to save the indirection when an instance has not had its class changed, or when a class has not been redefined. (These properties are dynamic - we take an indirection after changing the class of an instance, or redefining a class.)
13:20:45
hayley
Sure. I mention it as I'd still like to be able to optimise and inline methods assuming that the class of an instance does not change, but it seems CHANGE-CLASS would have to scan the stack to find code which now optimises based on false assumptions. Someone in #commonlisp might have a better idea though.
13:27:15
hayley
My gut feeling is that such stack scanning is acceptable for redefining a class, but not for changing the class of an instance. Maybe someone would also have an estimate of how frequently those operations occur, because nothing comes to my mind.
13:27:58
beach
Is there a lot of difference between the cases? In both cases the number of slots can change.
13:31:23
hayley
Even if the number of slots stays constant, I think we should make the instance use a new rack, to avoid strange behaviour around data races.
13:32:02
beach
So then I don't see a lot of difference between what needs to be done for change-class and for redefining a class.
13:35:26
hayley
There isn't a difference in what needs to be done. I suspect there is a difference in that typically only the programmer redefines classes, and such redefinitions are infrequent; but a program may change the classes of many instances.
13:35:44
hayley
So it would be acceptable for redefining a class to be somewhat slow, but less acceptable for change-class to be slow.
13:37:14
hayley
(Depending on the depth of the stack, "somewhat slow" is at worst in the milliseconds, I think. There's an idea - the stack scan could be made incremental using a "return barrier", and the barrier naturally batches up some work too.)
13:43:46
splittist
I would be wary of basing decisions on how efficient or quickly things need to be implemented on the basis of how things are done now - perhaps certain things are used now precisely because current implementations are inefficient.
13:47:14
hayley
We want to scan the stack to ensure that no functions on the call stack were compiled with any assumptions about the class of an instance, after we invalidated those assumptions. I don't think we have to do anything about the heap.
13:47:57
hayley
(This mechanism would be used in a JIT compiling system; maybe the relevant frames would be replaced with frames for deoptimised code.)
13:48:44
beach
I guess I am lost (as usual). If there is no indirection, and you redefine the class, then it would seem to me that every reference to the object would have to be updated.
13:54:09
hayley
Oh! You're right. There is an indirection, but the indirection is only followed when we try to use an instance, and the stamp of the instance somehow indicates that an indirection is necessary. The decision to follow an indirection or not could be part of method dispatch.
13:56:26
beach
I think you need to write this down in a form that can be read in full and commented upon.
13:57:19
beach
And your last sentence can be parsed in so many ways, I don't even know where to start.
13:58:07
beach
For instance "An indirection is used only when at least one class has been redefined"
14:00:32
hayley
It is only necessary to follow an indirection in an instance, when the class of the instance has been redefined.
14:03:12
hayley
The idea is basically the "partial read barrier" used in Smalltalk <https://dl.acm.org/doi/10.1145/2754169.2754186>, with the exceptions that the authors of that paper do not implement change-class, nor does their implementation need to be safe when using multiple threads.
14:06:07
hayley
What they call the "read barrier" is what we called the "indirection". The read barrier is "partial" in the sense that they try to avoid following the indirection, when it is not necessary to follow the indirection.
14:12:30
beach
Here is what I have understood so far: In the beginning there are no indirections because no class has been modified. At some point, it is then inevitable that a class will change. Since there are no indirections, all references must be updated. Yet, it is enough to scan the stack to find those references.
14:13:29
beach
But don't bother trying to explain it to me. The only way I can make sense of it is if it is written down in a coherent text that can be read in its entirety and commented upon.
14:14:46
gin
what is the syntax of melpa version numbers? I can see there is package-YYYYMMDD.NNN. What is the NNN? I thought it must be HHMM for hours minutes but why only 3 digits. what time formatting produces three digits for hours minutes?
14:15:00
hayley
I would recommend reading that paper then, until I get the time to write down how the technique would be adapted for a Common Lisp implementation.
14:23:09
hayley
I'm almost done with university for the semester, so hopefully I should be able to write my idea down soon. And hopefully I'll be able to finish off my parallel GC soon.
14:39:08
prokhor
hayley: do i understand it right: you plan to implement a compiler for a parallel language?
14:43:28
beach
prokhor: I know hayley has been working on a parallel garbage collector for SBCL, so that's probably what was referred to.
15:35:09
splittist
Would anyone like to share some OpenType font file reading code? I would like to play with CFF2 charstrings.
17:08:22
alcor
A few days ago, I read an internet that said CL conditions can be used to implement progress notification without unwinding the stack. Where can I find more info about this use case?
17:12:29
edwlan[m]
You'd just use (define-condition progress ...) to define the condition and then (signal 'progress ...) to signal progress
17:24:13
scymtym
my take from many years ago: https://github.com/scymtym/more-conditions#tracking-and-reporting-progress-of-operations
17:57:47
bitblit1
What are your opinions on recursive functions; when do you use them? all the time, completely avoid, other. If you do you them then what is your mindset meaning how do you solve a problem using recursive functions?
17:58:35
bitblit1
In your case is it harder to solve a problem using recursion rather than iterative solutions? Or same or other?
18:05:51
beach
bitblit1: As edwlan[m] says, you use recursion when your data is naturally inductive, except that you don't use recursion on linear structures like lists.
18:17:14
edwlan[m]
Like, if you're working with a list, you have a base case, (), and then a step case (x . rest)
18:17:54
edwlan[m]
So, it's often easier to work recursively because you can define how to handle the base case and how to handle the step case and then reduce handling rest to a recursive call
18:54:19
pjb
alcor: more details in the clcs book. (there's a #clcs channel too). https://www.amazon.com/Common-Lisp-Condition-System-Mechanisms/dp/148426133X