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(a)icloud.com>
> Subject: Re: Creating large arrays
> Date: July 18, 2019 at 2:45:14 PM MDT
> To: lisp(a)gmx.com
> Cc: lisp-hug(a)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.
>
>
>
>
> 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.
