freenode/#sicl - IRC Chatlog
Search
12:15:38
jcowan
beach: you might be interested in in how Chicken represents bignums; it is intended to minimize garbage collection, as bignum algorithms like Karatsuba * or Burnikel-Ziegler / tend to generate a lot of them
12:20:31
jcowan
A bignum is divided into an ordinary object and a data blob. The ordinary object is allocated in the nursery and the data blob is allocated in a separate specialized nursery called the scratch space. The object has a pointer to the blob; the blob in return contains the limbs (bigits), the sign, and a back-pointer to the object.
12:23:35
jcowan
When a bignum object is copied by the collector, the blob is copied to the new scratch space, but the scratch space need not be scanned at any time.
12:25:04
jcowan
No other pointers to the scratch space ever escape, and blobs are always 1-1 with bignum objects.
12:28:00
heisig
How would that be different (apart from maybe avoiding one more indirection) from representing bignums an object with an (unsigned-byte 64) vector for the data?
12:28:49
heisig
The (unsigned-byte 64) vector also doesn't need to be scanned by the GC, since it cannot contain pointers.
12:29:32
beach
jcowan: Thanks. It sounds complicated. Especially with the garbage collector(s) that I have in mind.
12:33:32
jcowan
heisig: Chicken originally had only fixnums and flonums in the core for the sake of efficiency, with bignum/ratio/complex support loadable from a library if you need it. The problem with this design is that files compiled without the bignum library could not even recognize bignums as numbers, so the idea was to put bignums in the core without sacrificing efficiency for code that didn't make use of them.
12:34:41
jcowan
The whole series (starting with ...-part-1.html) is very much worth reading for anyone interested in low-level representation in Lisps.
12:35:27
heisig
Yes, thanks jcowan for linking to this blog post! It contains a lot of interesting remarks and references.
12:36:52
jcowan
Gambit is similar to Chicken in many ways (CHicken was bootstrapped from Gambit before it became self-hosted)
12:38:18
jcowan
Note that "stack" in the Chicken context means the nursery, which is identified with the C stack.
12:40:37
jcowan
Chicken uses Henry Baker's Cheney-on-the-MTA algorithm, where (after CPS conversion) every procedure simply calls its successor, winding up the C stack. When it gets too big (there is a check at the beginning of each procedure), any data allocated in stack frames is copied to the heap, and a single longjmp() disposes of the whole C stack.