Making arrays from scratch

[Vebjorn Ljosa-4]

Hi,

I would like to make an mmapped file appear as a simple-array of
(unsigned-byte 8).  In SBCL, I can make this happen by putting an
appropriate header before the mmaped file in memory and then calling
sb-kernel:%make-lisp-obj on the address where the header starts.  Is
there something similar in CLISP?

Thanks,
Vebjorn

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Vebjorn Ljosa wrote:
> I would like to make an mmapped file appear as a simple-array of
> (unsigned-byte 8).  In SBCL, I can make this happen by putting an
> appropriate header before the mmaped file in memory and then calling
> sb-kernel:%make-lisp-obj on the address where the header starts.  Is
> there something similar in CLISP?

no, and not likely to be implementable because CLISP has a copying GC.
(actually Vladimir has introduced "pinned" objects not movable by GC for MT)
why do you want to do this?

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Vebjorn Ljosa-4]

Sam Steingold <sds@...> writes:

> no, and not likely to be implementable because CLISP has a copying GC.
> (actually Vladimir has introduced "pinned" objects not movable by GC
> for MT)

I was hoping it would be possible to have Lisp objects outside Lisp's
heap (do you call this "foreign space" in CLISP?) and therefore out of
the reach of the GC.

> why do you want to do this?

I need random access to a large number of cytometric measurements stored
in a file.  I would like to avoid reading the entire file into memory.
It would be convenient to simply index a Lisp array and leave it to the
memory manager to decide which chunks of the file to read and when, and
mmapping would accomplish that.

I noticed just now that CLISP's array dimension limit is only 2^24 - 1,
so the question of mmapping is moot, as I'll have to read chunks into
smaller arrays anyway.  

Thanks for responding.

Vebjorn

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Don Cohen-12]

Vebjorn Ljosa writes:

 > I noticed just now that CLISP's array dimension limit is only 2^24 - 1,
 > so the question of mmapping is moot, as I'll have to read chunks into
 > smaller arrays anyway.  
This limit is larger on 64 bit machines, so maybe not as moot as you
thought.  I've recently asked how hard it would be to increase the
limit but I didn't see any replies.  I'd very much like to see it
increased.  My view is that an array should be allowed to be close to
the size of VM.
I still think you can do what you want via FFI.
You probably can't treat the file as a lisp array, but I expect you'll
be able to write a similar accessing function taking a byte index and
returning a byte.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Don Cohen wrote:
> Vebjorn Ljosa writes:
>
>  > I noticed just now that CLISP's array dimension limit is only 2^24 - 1,
>  > so the question of mmapping is moot, as I'll have to read chunks into
>  > smaller arrays anyway.  
> This limit is larger on 64 bit machines, so maybe not as moot as you
> thought.  I've recently asked how hard it would be to increase the
> limit but I didn't see any replies.  I'd very much like to see it

Bruno should be able to elucidate this.
(as well an a sudden decrease in string size a few years ago).

> increased.  My view is that an array should be allowed to be close to
> the size of VM.

this is non-trivial since array limit constants are constrained to be fixnums
and clisp fixnums are 24 bits on 32-bit platforms and 48 bits on 64-bit ones.
(I don't see any reason for them to be less than 56 bits there though).


> I still think you can do what you want via FFI.
> You probably can't treat the file as a lisp array, but I expect you'll
> be able to write a similar accessing function taking a byte index and
> returning a byte.

you might want to take a look at the matlab interface where I have to access C
arrays from lisp.




-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Vladimir Tzankov]

Hi,
On Sep 25, 2008, at 6:29 PM, Sam Steingold wrote:

> Vebjorn Ljosa wrote:
>> I would like to make an mmapped file appear as a simple-array of
>> (unsigned-byte 8).  In SBCL, I can make this happen by putting an
>> appropriate header before the mmaped file in memory and then calling
>> sb-kernel:%make-lisp-obj on the address where the header starts.  Is
>> there something similar in CLISP?
>
> no, and not likely to be implementable because CLISP has a copying GC.
> (actually Vladimir has introduced "pinned" objects not movable by  
> GC for MT)
> why do you want to do this?
>

Pinned object will not help since there is no way to mmap file  
directly into lisp heap.
Since the lisp heap itself is mmap-ed (except in SPVW_PAGES) - the  
only way to implement memory mapped files is to have the mapping  
outside the heap. However the memory range at which the files can be  
mmap-ed should not interfere with lisp heap (that may grow and  
potentially overlap other mmap-ed regions).

Probably the best way to go is with FFI. You may look at Pascal  
Bourguignon's code: http://informatimago.com/develop/lisp/index.html 
(COM.INFORMATIMAGO.CLISP.RAW-MEMORY, COM.INFORMATIMAGO.COMMON-
LISP.MEMORY).

Vladimir

 

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Pascal J. Bourguignon]

Vebjorn Ljosa writes:

> Sam Steingold <sds@...> writes:
>
> > no, and not likely to be implementable because CLISP has a copying GC.
> > (actually Vladimir has introduced "pinned" objects not movable by GC
> > for MT)
>
> I was hoping it would be possible to have Lisp objects outside Lisp's
> heap (do you call this "foreign space" in CLISP?) and therefore out of
> the reach of the GC.
>
> > why do you want to do this?
>
> I need random access to a large number of cytometric measurements stored
> in a file.  I would like to avoid reading the entire file into memory.
> It would be convenient to simply index a Lisp array and leave it to the
> memory manager to decide which chunks of the file to read and when, and
> mmapping would accomplish that.
>
> I noticed just now that CLISP's array dimension limit is only 2^24 - 1,
> so the question of mmapping is moot, as I'll have to read chunks into
> smaller arrays anyway.  

So you don't need to mmap any lisp object.  I assume your cytometric
measurements are no lisp object.  Just mmap them and access the data
structure thru CFFI (or FFI).



Alternatively, you would need just a PEEK and a POKE (well, I guess
only a PEEK in this application).

http://darcs.informatimago.com/public/lisp/clisp/raw-memory.lisp
http://darcs.informatimago.com/public/lisp/clisp/raw-memory.c
http://darcs.informatimago.com/public/lisp/clisp/Makefile

There is little difference between (aref *mem* i) and (peek-uint8 (+ *mem* i)).
(And you can always wrap peek-uint8 in some mref to add bounds checking).





--
__Pascal Bourguignon__                     http://www.informatimago.com/

HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Bruno Haible]

> > I've recently asked how hard it would be to increase the
> > limit but I didn't see any replies.  I'd very much like to see it
>
> (as well an a sudden decrease in string size a few years ago).

The maximum size for arrays and strings is driven by the desire to have only
two header words per instance. It is a compromise. One could also choose to
have all arrays and all strings with three header words per instance. This
would increase the memory size by a certain percentage and the run time of
all programs by twice this percentage (according to Michael Monagan's
rule that when the memory use of a program increases by a factor X, its
use of time increases by a factor X^2).

So, assuming that not penalizing the _average_ program is important, we
have two header words. One is needed by the GC. The other one has to combine
the length and the following bits (see lispbibl.d for reference):
Arrays:
  - 8 bits are used for the type of array. Probably less bits would be sufficient,
    but as Sam mentioned, ARRAY-DIMENSION-LIMIT must be a fixnum. and
    MOST-POSITIVE-FIXNUM is 2^24-1. 24 = oint_data_len.
Strings:
  - 8 bits are used for the type of array, as above. Additionally, 2 bits are
    used to implement the automatic extension of width of a string: Strings
    exist in 8-bits-per-element, 16-bits-per-element, 32-bits-per-element
    flavours, and when a character is stored in a string of narrower width,
    the width is extended automatically. This process consumes 2 bits.

> > increased.  My view is that an array should be allowed to be close to
> > the size of VM.

You can write an abstraction of very long arrays, say in terms of an array
of arrays, in about 50 lines of code. With clisp's extensible sequences,
you can can even use the normal sequence functions on it. Refer to SYS::%DEFSEQ.

Bruno


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Don Cohen-12]

Bruno Haible writes:

 > The maximum size for arrays and strings is driven by the desire to have only
 > two header words per instance. It is a compromise. One could also choose to
 > have all arrays and all strings with three header words per instance. This
 > would increase the memory size by a certain percentage and the run time of
 > all programs by twice this percentage (according to Michael Monagan's
 > rule that when the memory use of a program increases by a factor X, its
 > use of time increases by a factor X^2).
I'm not familar with that rule.  What ever became of time/space tradeoffs?
Certainly there are lots of small arrays (especially strings), and it would
be nice to be able to represent them with low overhead.  
In fact, I suggest that for strings that are short enough, it would
make sense to have a representation analogous to fixnum, i.e., one
other 8 bit type code for short string.
By the time you get to large arrays, the difference between 2 and 3
header words doesn't matter.  So it would make sense to have another
type for large arrays.

 >     but as Sam mentioned, ARRAY-DIMENSION-LIMIT must be a fixnum. and
 >     MOST-POSITIVE-FIXNUM is 2^24-1. 24 = oint_data_len.
Even worse, array total size must be a fixnum.
I wonder why the writers of the spec made that decision.  (Any ideas?)
It seems absurd to me right now.
Perhaps there could be yet another type for BIG Arrays.
I know, I should implement that type in CLOS.
I'm tempted to do so.  If someone out there beats me to it I won't object.

 > You can write an abstraction of very long arrays, say in terms of
 > an array of arrays, in about 50 lines of code. With clisp's
 > extensible sequences, you can can even use the normal sequence
 > functions on it. Refer to SYS::%DEFSEQ.
I see, it might have been worth reading the rest of the message before
typing the last few sentences.
I guess I can't change functions like aref without violating the spec.
So I'd have to change my code to use the new functions.

Does anyone out there already have a very large array package?



-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Bruno Haible]

Don Cohen wrote:
> Even worse, array total size must be a fixnum.
> I wonder why the writers of the spec made that decision.  (Any ideas?)

A loop like    (dotimes (i (length array)) ...)
should not cons a bignum at every iteration. That would be a performance killer
in all implementations. That's the primary reason why fixnums exist in the
first place.

> What ever became of time/space tradeoffs?

You have a space/time tradeoff when you have two different algorithms, like
fuzzy search of a short pattern in a long text via linear search or via
an index.

Monagan's rule is valid when you don't change your algorithm, when you just
let it consume more memory.

> By the time you get to large arrays, the difference between 2 and 3
> header words doesn't matter.  So it would make sense to have another
> type for large arrays.

This would still have a performance overhead on every access of the small
arrays. Namely, at every AREF the code would have to distinuish the two
cases. It's not impossible to do, it's just a bit hard to implement it
in such a way that the cost for the many small arrays is low.

> Perhaps there could be yet another type for BIG Arrays.

If you want very big arrays with clisp on 32-bit machines, you can always
compile clisp with -DWIDE. It will be definitely slower, but has the big
arrays.

Bruno


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Pascal J. Bourguignon wrote:
>
> Alternatively, you would need just a PEEK and a POKE (well, I guess
> only a PEEK in this application).
>
> http://darcs.informatimago.com/public/lisp/clisp/raw-memory.lisp
> http://darcs.informatimago.com/public/lisp/clisp/raw-memory.c

actually, http://darcs.informatimago.com/public/lisp/clisp/raw-memory-lib.c 
because of ffi forms in raw-memory.lisp.
actually, raw-memory-lib.c is so small and simple that it could be folded into
raw-memory.lisp using c-lines.
(it is not because you support other lisp implementations too)

> http://darcs.informatimago.com/public/lisp/clisp/Makefile
>
> There is little difference between (aref *mem* i) and (peek-uint8 (+ *mem* i)).
> (And you can always wrap peek-uint8 in some mref to add bounds checking).


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Don Cohen wrote:
> Bruno Haible writes:
>
>  >     but as Sam mentioned, ARRAY-DIMENSION-LIMIT must be a fixnum. and
>  >     MOST-POSITIVE-FIXNUM is 2^24-1. 24 = oint_data_len.
> Even worse, array total size must be a fixnum.
> I wonder why the writers of the spec made that decision.  (Any ideas?)
> It seems absurd to me right now.

the rationale is pretty clear: iteration over arrays should not cons by itself,
so all array index computations must be done in the fixnum realm.
I think this is even spelled out in an issue write-up.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Bruno Haible wrote:
>>> I've recently asked how hard it would be to increase the
>>> limit but I didn't see any replies.  I'd very much like to see it
>> (as well an a sudden decrease in string size a few years ago).
>
>   - 8 bits are used for the type of array, as above. Additionally, 2 bits are
>     used to implement the automatic extension of width of a string: Strings
>     exist in 8-bits-per-element, 16-bits-per-element, 32-bits-per-element
>     flavours, and when a character is stored in a string of narrower width,
>     the width is extended automatically. This process consumes 2 bits.

but this begs a suggestion: just like there are 3 kinds of strings by element
type, there should be 2 kinds of arrays (and strings) by storage size.
i.e., 2-word-header small arrays and strings and 3-word-header big arrays ans
streams.


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Bruno Haible]

Sam wrote:
> but this begs a suggestion: just like there are 3 kinds of strings by element
> type, there should be 2 kinds of arrays (and strings) by storage size.
> i.e., 2-word-header small arrays and strings and 3-word-header big arrays

In my opinion, the 3 kinds of strings by element type were a strong requirement
(combining Unicode support with low memory use), whereas multi-megabyte arrays
and strings were not a strong requirement. If your opinion varies, feel free
to add strings and vectors that have 3 header words.

Bruno


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Sam Steingold]

Bruno Haible wrote:
> Sam wrote:
>> but this begs a suggestion: just like there are 3 kinds of strings by element
>> type, there should be 2 kinds of arrays (and strings) by storage size.
>> i.e., 2-word-header small arrays and strings and 3-word-header big arrays
>
> In my opinion, the 3 kinds of strings by element type were a strong requirement
> (combining Unicode support with low memory use), whereas multi-megabyte arrays
> and strings were not a strong requirement. If your opinion varies, feel free
> to add strings and vectors that have 3 header words.

do we have a spare flag bit for strings and arrays?



-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Hoehle, Joerg-Cyril]

Hi,

>> Alternatively, you would need just a PEEK and a POKE (well, I guess
>> only a PEEK in this application).
>>
>> http://darcs.informatimago.com/public/lisp/clisp/raw-memory.lisp
>> http://darcs.informatimago.com/public/lisp/clisp/raw-memory.c
>
>actually,
>http://darcs.informatimago.com/public/lisp/clisp/raw-memory-lib.c 
>because of ffi forms in raw-memory.lisp.
>actually, raw-memory-lib.c is so small and simple that it
>could be folded into raw-memory.lisp using c-lines.

Actually, you don't need any C functions for something as trivial.
1. You could play C-like tricks using WITH-C-VAR to pointer and CAST.
2. You could use MEMORY-AS.

That said, using a foreign function is fastest because you typically
avoid PARSE-C-TYPE at run-time (and you avoid producing a garbage
#<FOREIGN-ADDRESS> obejcts too). Still, you can manage to write peek and
poke using the "remember parse-c-type values at compile-time"-trick I
mentioned in this list moons ago, which would then be as fast as a
function call.

MEMORY-AS is just another word for PEEK, and (SETF MEMORY-AS) is POKE -
except of course, they take a foreign-pointers, not an integer as
address.

Using compiler macros, you could write PEEK&POKE based on MEMORY-AS
which would not even perform a CASE or table-based dispatch.
(define-compiler-macro peek-uint32 (integer-address)
  `(memory-as (unsigned-foreign-address ,integer-address)) (parse-c-type
'uint32))
The compiler-macro existing for PARSE-C-TYPE should eliminate its
invocation.

GC-cost: one #<FOREIGN-ADDRESS> per run-time invocation.

Note that using MEMORY-AS, you get vector conversion for free:  Much
faster than the DO loop Pascal implements in his PEEK and POKE
functions.
I believe Pascal's code predates the introduction of MEMORY-AS to
CLISP's FFI.
Use a type of `(array ,c-type ,(length obj)) as in
(memory-as <address> (parse-c-type `(array uint32 ,(* 17 42))))
(setf (memory-as ... (parse-c-type '(c-array uint8 4))) #(1 2 3 4))

That said, PEEK & POKE in CLISP is still an order of a magnitude slower
in CLISP than in anything that compiles to native code -- obviously.

Regards,
        Jorg Hohle.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list

[Hoehle, Joerg-Cyril]

Vebjorn Ljosa wrote:
>I noticed just now that CLISP's array dimension limit is only 2^24 - 1,
>so the question of mmapping is moot, as I'll have to read chunks into
>smaller arrays anyway.  
That's no reason. You can still use mmap and do something similar to
windowing.

To make a decision as to your implementation path, you'll have to think
about what's important to you:
o raw speed?
o portabity?
o ease of use?
o understandability of code?

Then you can go for mixtures of what's been proposed in this and the
other thread,
o Use your own primitive access functions;
o Use block-based accessors, instead of element by elt.;
o Use CLtL sequence functions using CLISP's DEFSEQ extension, delegating
to MEM-READ (note that CLISP's sequence functions are overly "generic"
and hence not quite fast).

I once wrote the ~50-100 lines required for providing an FFI-based-array
<-> Lisp sequence integration via DEFSEQ.
The one open issue I remember was the unclear semantics of copying such
an array: What is SUBSEQ on a mmap'ed array (or any FFI array, for that
matter)?

Regards,
        Jorg.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
clisp-list mailing list
clisp-list@...
https://lists.sourceforge.net/lists/listinfo/clisp-list