guile-user
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: are double cells safe to use?


From: Roland Orre
Subject: Re: are double cells safe to use?
Date: Tue, 29 Oct 2013 19:04:14 +0100

Thanks,

> So the best you could do with a double cell would be to store three SCM
> objects, which is no better space efficiency than you already get with a
> vector of size 3 (in the master branch, which will become Guile 2.2).

but with the vector I also have an extra cell (single?) pointing to the vector.
For this kind of things I've earlier always used records (with new smobs)
or vectors, but now I wanted to make it as space efficient as possible.
It'll be a memory based database which will be "static" (re-indexed daily,
Day-Stout-Warren trees) and contain  (in the long run..., billions of records)

I guess the best alternative then is to use smob with e.g. a 4-word
(SCM) vector.
which implies 6 scm_t_bits, but if a 4 word vector is equally space
efficient I may
better go for that.


On Tue, Oct 29, 2013 at 6:17 PM, Mark H Weaver <address@hidden> wrote:
> Roland Orre <address@hidden> writes:
>
>> I consider using double cells for efficient implementation of binary trees.
>>
>> Is this safe? (i.e. no pre-assumptions made somewhere what these are used 
>> for)
>>
>> For prototyping I intended to add
>> double-cons
>> set-cbr!
>> set-ccr!
>> cbr
>> ccr
>>
>> to the scheme level. Is this safe?
>
> No, this won't work.  First of all, double cells cannot be used to store
> four SCM values, because the first word of a double cell has to contain
> the type tag.  Pairs avoid the type tag by the clever hack: the low bit
> of every SCM value is 0, so if the first word of a heap object has 0 in
> the low bit, that heap object is assumed to be a pair.  But this means
> that every other heap object must start with a word whose low bit is 1.
>
> So the best you could do with a double cell would be to store three SCM
> objects, which is no better space efficiency than you already get with a
> vector of size 3 (in the master branch, which will become Guile 2.2).
>
> Another problem with creating yet another new fundamental data type is
> that in order to use it efficiently, we'd need to create more VM
> instructions to access it.  That means more opcodes from our limited
> 8-bit opcode space, and more code in the VM, which is bad because
> ideally a VM should be compact for good cache behavior.
>
> I think you should just use records, or maybe vectors, for this.
>
>      Mark



reply via email to

[Prev in Thread] Current Thread [Next in Thread]