Hello,

Someone on the LISP HUG Mailing list was recently trying to allocate a 4GB array and found that it was failing.  I was recently thinking about such problems wishing there were sparse arrays in CL; I ended up making something called ’Spaces’ which potentially solve the problem.

Below is a letter to HUG that I sent to someone outlining my solution to the problem.

I thought some of you might find it useful as well, or might want to discuss this data structure, which I think is new, or at least I have never read nor heard of it before I invented it a couple of months ago.

Burton

Begin forwarded message:

From: Burton Samograd <busfactor1@icloud.com>
Subject: Re: Creating large arrays
Date: July 18, 2019 at 2:45:14 PM MDT
To: lisp@gmx.com
Cc: lisp-hug@lispworks.com


Are there other fast-access data structures with no such limitations, on
LispWorks?


Thank you again,

Priyadarshan

I have created something called ’N-Dimensional Sparse Spaces’ as a solution to the large array allocation problem.  


No photo description available.

This initial implementation is one to replace a set of random points within an N-Dimensional Sparse Grid addressed using integers, hence the use of #’= in #’make-space.

It is more generallized using other equals functions such as #’eql (so you can use symbols, and hence make an addressable symbol space), #’equals and #equalp letting you use S-Expressions as your addresses.

I have a more general implementation somewhere in my code, but the above image is the code I initially wrote that can be springboarded off of to create your own implementation.

One trick I have thought of is to, after you have completed your work with the space, is to compile it to a more suituable data structure for read-only access.

The sparce space is for editing and loading of the data you want to work with.  A complied space is for reading data from the space, giving up generality.

Feel free to write me to discuss this data structure further if you have any questions or comments on its usefulness and generality and applicability to your problem.

Burton Samograd
BusFactor1 Inc.