are double cells safe to use?

are double cells safe to use?

[Roland Orre]

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?
They will only contain or refer to SCM data types.

Of course I could add an own datatype, but as double cells contains
exactly what I need and they are used internally I consider them being
the obvious choice.

I wrote to both user and devel as I consider this may be more of a
devel question.

Re: are double cells safe to use?

[Roland Orre]

Sorry, double cells are even encouraged to use according the manual under
"Allocating cells"  (I had missed that)
and no specific cares as long as they contain only SCM.

On Tue, Oct 29, 2013 at 11:15 AM, Roland Orre <roland.orre@gmail.com> wrote:
> 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?
> They will only contain or refer to SCM data types.
>
> Of course I could add an own datatype, but as double cells contains
> exactly what I need and they are used internally I consider them being
> the obvious choice.
>
> I wrote to both user and devel as I consider this may be more of a
> devel question.

Re: are double cells safe to use?

[Ludovic Courtès]

Hi,

Roland Orre <roland.orre@gmail.com> skribis:

> Sorry, double cells are even encouraged to use according the manual under
> "Allocating cells"  (I had missed that)
> and no specific cares as long as they contain only SCM.

Well, that part of the manual is slightly deprecated.  ;-)

I’d recommend using an appropriate data type instead.  If the code you
write is in Scheme, you’d better use records (info "(guile) Record
Overview").

If the code is in C, you’d better use ‘scm_gc_malloc’ and allocate as
much room as needed to hold your C struct.

HTH!

Ludo’.

Re: are double cells safe to use?

[Mark H Weaver]

Roland Orre <roland.orre@gmail.com> 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

Re: are double cells safe to use?

[Roland Orre]

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 <mhw@netris.org> wrote:
> Roland Orre <roland.orre@gmail.com> 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