Re: Sequences?
Ryan Zerby asks:
> How are sequences implemented in Euphoria, anyway?
As you are probably aware, Euphoria (ex.exe/exw.exe)
is written in C. Therefore a Euphoria sequence has to be
represented in memory using C data structures. The way
that a sequence is represented has changed several times
over the years, without requiring any Euphoria code to
be rewritten, and in most cases without anyone even noticing.
I started off with the notion that sequences were like Lisp
lists and should therefore be implemented using linked
lists. This carried a lot of memory overhead for the links,
and made subscripting quite slow, so I rewrote the whole
interpreter to make sequences more like arrays.
Several iterations later we now have the current
structure (which changed again slightly in 1.5a).
Sequences are currently implemented as a header,
followed by an array of 4-byte values. 1 bit in each
value tells the interpreter whether the value is an
integer or a pointer to something. That's why the
Euphoria integer type is 31-bits, not 32. If it's a pointer
to something it will point at either another sequence,
or a floating-point number.
The header contains a reference count, the length of
the sequence, and some storage allocation info designed
to make it easier to append, prepend and concatenate
without necessarily having to copy the whole sequence
to a bigger area in memory.
Regards,
Rob Craig
Rapid Deployment Software
|
Not Categorized, Please Help
|
|
