gsg · HackerTrans

This works until the analogue of monotremes shows up to ruin your supposedly flawless categorisation.

System F doesn't have general recursion.

Extensions with a letrec-like construct are common, and are sometimes inaccurately called 'System F', but those languages do not have the properties of System F.

gsg

5 lat temudiscuss

There are some examples, for example Crowbar is an OCaml tool that uses AFL to drive property based tests.

gsg

5 lat temudiscuss

chrisseaton is talking about the bump-pointer allocator in a modern GC, not an implementation of malloc/free. The performance characteristics are quite different.

In a generational copying system an object that is bump allocated and then is dead before being copied out of the young generation is indeed cheap - dead objects in the young generation don't need to be freed or even looked at in any way because the space for the young generation can simply be reused after everything is copied out of it. The slow part is elsewhere.

gsg

5 lat temudiscuss

Yes, this has been done a few times. CDR-coding was a hardware-assisted method of unrolling a Lisp list (complicated somewhat by the need to support mutation of car and cdr) that appeared on Lisp machines, and there's a Appel/Reppy/Shao paper on unrolling linked lists in the context of Standard ML.

There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf

gsg

5 lat temudiscuss

You can easily see by searching for 'kmalloc' (or 'malloc') at https://github.com/torvalds/linux/blob/master/include/linux/... that it does no such thing.

Here's the logic for adding a list node:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
            if (!__list_add_valid(new, prev, next))
                    return;

            next->prev = new;
            new->next = next;
            new->prev = prev;
            WRITE_ONCE(prev->next, new);
    }

No allocation, just mutating some fields in preexisting list_head structures. Those are by convention stored as a field in whatever struct needs to be kept in the list, which is what 'intrusive' means.

gsg

6 lat temudiscuss

BOUND is pretty slow, and requires an odd start/end pair to be placed in memory. I don't see any reason that it would be better than the usual unsigned comparison + branch that languages with bounds checking tend to use.

Besides, much of the difficulty with memory safety in C and C++ is the existence of pointers (or wrappers around them, like iterators), which do not come with an associated length. Length checking machinery can't help with that problem whether special instructions exist or not.

In short, it's doubtful that the availability of these old instructions would make any difference to the practicality of bounds checking on modern x86 machines whatsoever.

gsg

6 lat temudiscuss

Sure, but that didn't change much between x86 and x86-64. Perhaps it got a little worse because the SIMD instructions aren't overflow check friendly.

gsg

6 lat temudiscuss

That still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.

gsg

8 lat temudiscuss

This is nonsense. Modern compilers don't work by generating the results you see with -O0 and then optimising; the poor quality of -O0 code is the result of skipping register allocation.

> Dataflow-directed, "work backwards" techniques might be the solution

Destination driven code generation is a known technique. It doesn't generate good enough results to have gotten much attention (better than what you get from -O0, though).

gsg

11 lat temudiscuss

Fast, restrictive and secure have been done before - see ATS, Cyclone, etc. Almost everybody ignored those trailblazing efforts, probably because those languages are very intimidating.

comments