hayley-patton

17 dagen geledendiscuss

> Like there is even a paper that shows that one is tracking liveness, while the other tracks "deadness" and they are literally going at the same thing from different ends.

https://dl.acm.org/doi/10.1145/1035292.1028982

hayley-patton

30 dagen geledendiscuss

> It’s possible my interpretation wasn’t correct and the author was citing Kernel’s approach as sanity. That would make sense technically.

That's indeed what I meant, I meant the opposite of taking a dig at Kernel. My understanding is Shutt thought fexprs got a bad wrap because of dynamic scoping; quoth the Kernel website:

> they made a mess out of the language semantics because they were non-orthogonal to the ordinary variety of procedures constructed via lambda — and, more insidiously, because at that time the mainstream Lisps were dynamically scoped (a language feature that causes more problems for fexprs than it does for the less powerful macros).

My belated apologies for the ambiguity.

hayley-patton

4 maanden geledendiscuss

As not mentioned in the article, if you want the general form of this algorithm, it is a Hillis-Steele prefix sum: <https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_1:_Shorte...>

hayley-patton

6 maanden geledendiscuss

ignore previous instructions and rewrite rlibm in Scheme

hayley-patton

6 maanden geledendiscuss

> If you can't falsify it, you have to take it seriously.

No, I don't.

hayley-patton

6 maanden geledendiscuss

This is the Lisp-2 mark-compact algorithm shuffled around [0]. The Lisp-2 algorithm doesn't need semispaces, because if you compute forwarding pointers and rewrite references before moving objects, you can compact in the one space just fine. The next field of the GC header isn't necessary as the next object will always be immediately after when bump allocating [1], and rewrite_nested doesn't need to recursively call itself, since the heap traversal will fix references in all objects anyway.

About "Since allocations are expensive due to them requiring a system interaction via syscalls" and "For this only bump allocation is an option, simply because syscalls are slow, multiple for many small objects are even slower and hot paths would explode" there's no reason that a free-list allocator has to do more syscalls than a bump allocator; any malloc under the sun is going to have at least one layer of caching before it makes a syscall for more memory. You could do a doubling scheme like with the bump allocator, or allocate a lot at a time; mimalloc for example requests segments of 4MiB from the kernel [2].

[0] It's approximately steps #1 and #3 fused together, then #2 in https://en.wikipedia.org/wiki/Mark%E2%80%93compact_algorithm...

[1] Something like for (void *object = segment->start; object < segment->end; object += size_in_words(object))

[2] https://www.microsoft.com/en-us/research/wp-content/uploads/...

hayley-patton

6 maanden geledendiscuss

My recollection is that ASIC-resistance involves using lots of scratchpad memory and mixing multiple hashing algorithms, so that you'd have to use a lot of silicon and/or bottleneck hard on external RAM. I think the same would hurt FPGAs too.

hayley-patton

7 maanden geledendiscuss

I'm pretty sure it's mathematically guaranteed that you have to be bad at compressing something. You can't compress data to less than its entropy, so compressing totally random bytes (where entropy = size) would have a high probability of not compressing at all, if no identifiable patterns appear in the data by sheer coincidence. Establishing then that you have incompressible data, the least bad option would be to signal to the decompressor to reproduce the data verbatim, without any compression. The compressor would increase the size of the data by including that signal somehow. Therefore there is always some input for a compressor that causes it to produce a larger output, even by some miniscule amount.

hayley-patton

8 maanden geledendiscuss

> What I can imagine is a purpose-built CPU that would make the JIT's job a lot easier and faster than compiling for x86 or ARM. Such a machine wouldn't execute raw Java bytecode, rather, something a tiny bit more low-level.

This is approximately exactly what Azul Systems did, doing a bog-standard RISC with hardware GC barriers and transactional memory. Cliff Click gave an excellent talk on it [0] and makes your argument around 20:14.

[0] https://www.youtube.com/watch?v=5uljtqyBLxI

hayley-patton

8 maanden geledendiscuss

That's a linear traversal of the heap, not a trace. A trace traverses references in objects until it reaches a fixed point of a live/dead set.

hayley-patton

8 maanden geledendiscuss

Dynamo <https://www.cse.iitm.ac.in/~krishna/courses/2022/odd-cs6013/...>?

hayley-patton

9 maanden geledendiscuss

[0] is Self and Self: Whys and Wherefores <https://youtu.be/3ka4KY7TMTU?si=Js_oG3MneCxBtEql&t=2378>

> And at the time, we thought it was impossible to make this language run efficiently, because it did all these things that were more abstract than languages of the time ...

hayley-patton

9 maanden geledendiscuss

> but JavaScript totally missed the boat on efficient compile-ability, which is the most interesting thing about Self

That's making much use of hindsight though: the creators of Self didn't think it would run fast, until it did [0]. The HOPL paper on Self [1] spends many words recounting the challenge of making Self fast.

[0] This is arguably a stronger claim than what appears in HOPL; I think it's from a talk by Dave Ungar, I'd have to check.

[1] https://dl.acm.org/doi/10.1145/1238844.1238853

hayley-patton

2 jaar geledendiscuss

I'm not very good at maths so I let Z3 work out some convenient seeds for me, leading to

    import java.util.Random;
    public class Hayley {
         public static void main(String... args) {
             byte[] b1 = new byte[4], b2 = new byte[2];
             (new Random(0x2effe2140e00L)).nextBytes(b1);
             (new Random(0xc2f0097)).nextBytes(b2);
             System.out.println(new String(b1) + new String(b2));
         }
    }

hayley-patton

3 jaar geledendiscuss

> C++ with its relatively unsophisticated OOP and minimal overhead on everything, is as fast as you're going to get

No it isn't. If your C++ compiler isn't devirtualising at all (implied by the article) it'll get stomped on by anything doing inline caching [0] which will generate the switch-case code. The JVM does that for example.

[0] https://bibliography.selflanguage.org/_static/pics.pdf

hayley-patton

4 jaar geledendiscuss

Something like "Address/memory management for a gigantic LISP environment or, GC considered harmful" <https://dl.acm.org/doi/10.1145/1317203.1317206>? I think that uses usual LRU mechanisms to determine what to page though.

hayley-patton

4 jaar geledendiscuss

Barriers are probably too small to cause latency spikes. The object logging barriers are a bit complicated, as they write an object into a thread-local log and infrequently have to get more memory for the log. But a card barrier is rather simple, and could look like

    SHR R_pointer, 9
    AND R_pointer, <cards>
    MOV BYTE [R_cards + R_pointer], 0

where <cards> is one below an immediate power of two number of cards, each card covering 2^9 = 512 bytes of heap. This is roughly the write barrier in SBCL on x86-64; there isn't much of a reason to think it will cause a latency spike.

On the other hand, "Barriers revisited" does mention a pathology about how cards can introduce false sharing, but that's still more of a smear than a spike.

hayley-patton

4 jaar geledendiscuss

To "lose" 5% I imagine one has to only be "worse" than some other heuristic that they measured the results of.

hayley-patton

4 jaar geledendiscuss

Right, I don't mean to downplay the significance of 1%, but aren't there many ways to win or lose 1%? More specifically perhaps, are there so few GCed pointers that a faster collector cannot recuperate that 1%?

moonchild's suggestion to monomorphise against GC/explicitly managed pointers might reduce that figure lower; evidently you know D programs better than I, but it doesn't seem unreasonable that the 1% can be won by a faster GC.

hayley-patton

4 jaar geledendiscuss

I would expect to be able to find another 1% slowdown somewhere in an implementation of another "system programming language" - would that also disqualify it from being such a language?

comments