Jeff Barnett <jbb@notatt.com> writes:

> On 2/11/2024 3:38 AM, Ben Bacarisse wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 2/11/2024 12:00 AM, Alan Bawden wrote:
>>>> Julieta Shem <jshem@yaxenu.org> writes:
>>>> Vectors are not convenient when we want to build something one
>>>> element
>>>> at a time. I think coercing a list into a vector is O(n), but that
>>>> seems inevitable because to make a vector we need to know the size and
>>>> we don't know the size up front.
>>>> This is why we have arrays with fill pointers. You should read up on
>>>> how arrays (and vectors) really work, with an eye on eventually being
>>>> able to use VECTOR-PUSH-EXTEND on a array that's specialized to contain
>>>> just 8-bit bytes.
>>>
>>> N.B. The use of vector-push-extend, where extend happens many (for many
>>> definitions of "many") times, will consume O(n^2) time AND probably memory
>>> too. There is no free (or even cheap) lunch when you don't have a good
>>> estimate of final total size up front.
>> Is this true for real implementations? I would have thought they would
>> typically use an exponential allocation strategy to give what is often
>> called "amortised O(n)" growth.
>> That is certainly what I found in a quick experiment using clisp:
>> (defun build-vec (size)
>> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
>> (dotimes (i size (length a)) (vector-push-extend i a))))
>> shows linear growth in execution time.
>
> Every time you do a rebuild initiated by a push-extend you end up copying
> all the current items in the vector;

Why? Having to copy everything, even in a tight reallocation loop like
the one I used, will be a problem.

> and each time you do the copy, more
> items are copied than for the last copy. This leads, finally, to O(n^2)
> complexity. And as to storage, you must look at all the allocations you
> have done and the overhead to either GC or tack them into your
> heap. Usually, you only notice this degradation if you push a whole lot of
> items - recall, O(.) is really an asymptotic measure. Lots of tricks will
> hide the problem for a while but one usually gets bit in the end.
>
> When you ran build-vec, did you let size be a few billion? What
> happened to run time?

No, I could only go up to (expt 2 23) before clisp seg faulted (surely a
bug?). That's only about 8 million items, but 134 million bytes of
storage. The time taken was almost perfectly linear.

> My guess is that most storage heap management schemes take about
> the same amount of time and storage to allocate a few bytes and a few
> thousand bytes. The growth effect, if it is real in the implementation you
> are using for testing, must build vectors many many times longer than the
> internal allocation chunk size to see the quadratic effect.

Can you post an example? I don't know how to get either clisp or SBCL
to go much larger. They both have options which would seem to control
this but I can't seem to get them to cooperate! Any help would be much
appreciated.

--
Ben.

On Sun, 11 Feb 2024 10:38:45 +0000
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Is this true for real implementations? I would have thought they would
> typically use an exponential allocation strategy to give what is often
> called "amortised O(n)" growth.
>
> That is certainly what I found in a quick experiment using clisp:
>
> (defun build-vec (size)
> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
> (dotimes (i size (length a)) (vector-push-extend i a))))
>
> shows linear growth in execution time.

[17]> (build-vec 16000000)

*** - VECTOR-PUSH-EXTEND: extending the vector by 8388608 elements makes it too long
The following restarts are available:
ABORT :R1 Abort main loop
Break 1 [18]> :r1
[19]> most-positive-fixnum
16777215

I tried the following variation :

(defvar b 11)

(defun build-vec (size)
(let ((a (make-array 0 :adjustable t :fill-pointer t)))
(dotimes (i size (length a)) (setq b i) (vector-push-extend i a))))

I get the same error message and in the debugger the value of b is
8388608. These experiments suggest an exponential reallocation policy.

--
vlaho.ninja/menu

On 2/12/2024 1:53 PM, Ben Bacarisse wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 2/11/2024 3:38 AM, Ben Bacarisse wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> On 2/11/2024 12:00 AM, Alan Bawden wrote:
>>>>> Julieta Shem <jshem@yaxenu.org> writes:
>>>>> Vectors are not convenient when we want to build something one
>>>>> element
>>>>> at a time. I think coercing a list into a vector is O(n), but that
>>>>> seems inevitable because to make a vector we need to know the size and
>>>>> we don't know the size up front.
>>>>> This is why we have arrays with fill pointers. You should read up on
>>>>> how arrays (and vectors) really work, with an eye on eventually being
>>>>> able to use VECTOR-PUSH-EXTEND on a array that's specialized to contain
>>>>> just 8-bit bytes.
>>>>
>>>> N.B. The use of vector-push-extend, where extend happens many (for many
>>>> definitions of "many") times, will consume O(n^2) time AND probably memory
>>>> too. There is no free (or even cheap) lunch when you don't have a good
>>>> estimate of final total size up front.
>>> Is this true for real implementations? I would have thought they would
>>> typically use an exponential allocation strategy to give what is often
>>> called "amortised O(n)" growth.
>>> That is certainly what I found in a quick experiment using clisp:
>>> (defun build-vec (size)
>>> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
>>> (dotimes (i size (length a)) (vector-push-extend i a))))
>>> shows linear growth in execution time.
>>
>> Every time you do a rebuild initiated by a push-extend you end up copying
>> all the current items in the vector;
>
> Why? Having to copy everything, even in a tight reallocation loop like
> the one I used, will be a problem.
>
>> and each time you do the copy, more
>> items are copied than for the last copy. This leads, finally, to O(n^2)
>> complexity. And as to storage, you must look at all the allocations you
>> have done and the overhead to either GC or tack them into your
>> heap. Usually, you only notice this degradation if you push a whole lot of
>> items - recall, O(.) is really an asymptotic measure. Lots of tricks will
>> hide the problem for a while but one usually gets bit in the end.
>>
>> When you ran build-vec, did you let size be a few billion? What
>> happened to run time?
>
> No, I could only go up to (expt 2 23) before clisp seg faulted (surely a
> bug?). That's only about 8 million items, but 134 million bytes of
> storage. The time taken was almost perfectly linear.
>
>> My guess is that most storage heap management schemes take about
>> the same amount of time and storage to allocate a few bytes and a few
>> thousand bytes. The growth effect, if it is real in the implementation you
>> are using for testing, must build vectors many many times longer than the
>> internal allocation chunk size to see the quadratic effect.
>
> Can you post an example? I don't know how to get either clisp or SBCL
> to go much larger. They both have options which would seem to control
> this but I can't seem to get them to cooperate! Any help would be much
> appreciated.

At the moment I have no system to build executable code. About a year
ago, I contacted Franz Lisp to see what they wanted for a non commercial
license - what they used to lease to me years ago as some sort of
academic thing. Unfortunately, the price was more than I wanted to pay
to putter around so I passed. At present, I'm working from the back of
an envelope:

I don't know if it will help but I'll tell you a few of the assumptions
I made leading to what I wrote above.

1. Most variants of push-extend want to maintain the use of indexing to
find the nth entry. That basically means that you demand that all memory
used be contiguous (in the address space). There are ways around this by
using heap (as in heap sort) algorithms but retrieval times go from O(1)
to O(log size).

2. Many variants of Malloc/Free set a minimum size, under the table, for
the blocks they actually maintain: a size like 256 bytes or the same
size as the virtual address mechanism handles, e.g., 4k bytes. If this
is the case, you need REALLY big test cases that get to the point where
you go quadratic in these size chunks.

3. If you have a good handle on the structure (its ultimate size, growth
characteristics, and reference patterns) you can develop or find
algorithms that are better than I'm estimating above. However and this
is were the gotchas come in, using these specialized approaches in
something like a general purpose Lisp push-extend primitive is all
wrong: the overhead will eat little applications alive and cause one to
wonder what's wrong with the system. Microseconds will turn into
milliseconds, etc. Of course one could take the same approach taken by
most Lisp hash packages: implement hash as an object type that can not
only grow but morph its type as the table gets larger. For example, a
hash table is originally implemented (under the table) as an assoc list;
when the number of items crosses a threshold another set of methods
provide hash functionality. And so on.
--
Jeff Barnett

Jeff Barnett <jbb@notatt.com> writes:

> On 2/12/2024 1:53 PM, Ben Bacarisse wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 2/11/2024 3:38 AM, Ben Bacarisse wrote:
>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>
>>>>> On 2/11/2024 12:00 AM, Alan Bawden wrote:
>>>>>> Julieta Shem <jshem@yaxenu.org> writes:
>>>>>> Vectors are not convenient when we want to build something one
>>>>>> element
>>>>>> at a time. I think coercing a list into a vector is O(n), but that
>>>>>> seems inevitable because to make a vector we need to know the size and
>>>>>> we don't know the size up front.
>>>>>> This is why we have arrays with fill pointers. You should read up on
>>>>>> how arrays (and vectors) really work, with an eye on eventually being
>>>>>> able to use VECTOR-PUSH-EXTEND on a array that's specialized to contain
>>>>>> just 8-bit bytes.
>>>>>
>>>>> N.B. The use of vector-push-extend, where extend happens many (for many
>>>>> definitions of "many") times, will consume O(n^2) time AND probably memory
>>>>> too. There is no free (or even cheap) lunch when you don't have a good
>>>>> estimate of final total size up front.
>>>> Is this true for real implementations? I would have thought they would
>>>> typically use an exponential allocation strategy to give what is often
>>>> called "amortised O(n)" growth.
>>>> That is certainly what I found in a quick experiment using clisp:
>>>> (defun build-vec (size)
>>>> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
>>>> (dotimes (i size (length a)) (vector-push-extend i a))))
>>>> shows linear growth in execution time.
>>>
>>> Every time you do a rebuild initiated by a push-extend you end up copying
>>> all the current items in the vector;
>> Why? Having to copy everything, even in a tight reallocation loop like
>> the one I used, will be a problem.
>>
>>> and each time you do the copy, more
>>> items are copied than for the last copy. This leads, finally, to O(n^2)
>>> complexity. And as to storage, you must look at all the allocations you
>>> have done and the overhead to either GC or tack them into your
>>> heap. Usually, you only notice this degradation if you push a whole lot of
>>> items - recall, O(.) is really an asymptotic measure. Lots of tricks will
>>> hide the problem for a while but one usually gets bit in the end.
>>>
>>> When you ran build-vec, did you let size be a few billion? What
>>> happened to run time?
>> No, I could only go up to (expt 2 23) before clisp seg faulted (surely a
>> bug?). That's only about 8 million items, but 134 million bytes of
>> storage. The time taken was almost perfectly linear.
>>
>>> My guess is that most storage heap management schemes take about
>>> the same amount of time and storage to allocate a few bytes and a few
>>> thousand bytes. The growth effect, if it is real in the implementation you
>>> are using for testing, must build vectors many many times longer than the
>>> internal allocation chunk size to see the quadratic effect.
>> Can you post an example? I don't know how to get either clisp or SBCL
>> to go much larger. They both have options which would seem to control
>> this but I can't seem to get them to cooperate! Any help would be much
>> appreciated.
....
> I don't know if it will help but I'll tell you a few of the assumptions I
> made leading to what I wrote above.

Thanks for what you wrote, but I was hoping for some help to extend my
tests so I could see the effects you think I should be seeing but which I
was not. I saw linear growth up to the point where the implementations
crapped out and I could not see how to extend them.

By the way, I don't think one can assume that in-place reallocation with
an exponential growth strategy in always going to be in place. I was
just suggesting that's it's likely to be what is used in some
implementations.

--
Ben.

On 2/13/2024 7:13 AM, Ben Bacarisse wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 2/12/2024 1:53 PM, Ben Bacarisse wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> On 2/11/2024 3:38 AM, Ben Bacarisse wrote:
>>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>>
>>>>>> On 2/11/2024 12:00 AM, Alan Bawden wrote:
>>>>>>> Julieta Shem <jshem@yaxenu.org> writes:
>>>>>>> Vectors are not convenient when we want to build something one
>>>>>>> element
>>>>>>> at a time. I think coercing a list into a vector is O(n), but that
>>>>>>> seems inevitable because to make a vector we need to know the size and
>>>>>>> we don't know the size up front.
>>>>>>> This is why we have arrays with fill pointers. You should read up on
>>>>>>> how arrays (and vectors) really work, with an eye on eventually being
>>>>>>> able to use VECTOR-PUSH-EXTEND on a array that's specialized to contain
>>>>>>> just 8-bit bytes.
>>>>>>
>>>>>> N.B. The use of vector-push-extend, where extend happens many (for many
>>>>>> definitions of "many") times, will consume O(n^2) time AND probably memory
>>>>>> too. There is no free (or even cheap) lunch when you don't have a good
>>>>>> estimate of final total size up front.
>>>>> Is this true for real implementations? I would have thought they would
>>>>> typically use an exponential allocation strategy to give what is often
>>>>> called "amortised O(n)" growth.
>>>>> That is certainly what I found in a quick experiment using clisp:
>>>>> (defun build-vec (size)
>>>>> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
>>>>> (dotimes (i size (length a)) (vector-push-extend i a))))
>>>>> shows linear growth in execution time.
>>>>
>>>> Every time you do a rebuild initiated by a push-extend you end up copying
>>>> all the current items in the vector;
>>> Why? Having to copy everything, even in a tight reallocation loop like
>>> the one I used, will be a problem.
>>>
>>>> and each time you do the copy, more
>>>> items are copied than for the last copy. This leads, finally, to O(n^2)
>>>> complexity. And as to storage, you must look at all the allocations you
>>>> have done and the overhead to either GC or tack them into your
>>>> heap. Usually, you only notice this degradation if you push a whole lot of
>>>> items - recall, O(.) is really an asymptotic measure. Lots of tricks will
>>>> hide the problem for a while but one usually gets bit in the end.
>>>>
>>>> When you ran build-vec, did you let size be a few billion? What
>>>> happened to run time?
>>> No, I could only go up to (expt 2 23) before clisp seg faulted (surely a
>>> bug?). That's only about 8 million items, but 134 million bytes of
>>> storage. The time taken was almost perfectly linear.
>>>
>>>> My guess is that most storage heap management schemes take about
>>>> the same amount of time and storage to allocate a few bytes and a few
>>>> thousand bytes. The growth effect, if it is real in the implementation you
>>>> are using for testing, must build vectors many many times longer than the
>>>> internal allocation chunk size to see the quadratic effect.
>>> Can you post an example? I don't know how to get either clisp or SBCL
>>> to go much larger. They both have options which would seem to control
>>> this but I can't seem to get them to cooperate! Any help would be much
>>> appreciated.
> ...
>> I don't know if it will help but I'll tell you a few of the assumptions I
>> made leading to what I wrote above.
>
> Thanks for what you wrote, but I was hoping for some help to extend my
> tests so I could see the effects you think I should be seeing but which I
> was not. I saw linear growth up to the point where the implementations
> crapped out and I could not see how to extend them.
>
> By the way, I don't think one can assume that in-place reallocation with
> an exponential growth strategy in always going to be in place. I was
> just suggesting that's it's likely to be what is used in some
> implementations.

I wasn't assuming an in-place reallocation. My thoughts were more along
the following lines:

An implementation of a vector with extend potential must still properly
allow all vector methods (as in object methods) to meet their original
contract. So, for example, the vector must present at least the illusion
of elements being consecutive in the address space. In Lisp it also
means that one can (after doing appropriate index validation) access the
vector by computing its address in most implementations. One can do
better by ignoring such "requirements" but then the implementation will
display some kinks. It's just easier to assign new contiguous address
space to the vector, copy the old contents, then put a magic forwarded
pointer in the original header, and leave the rest of the original so
the GC can have at.

I'm not sure if I understood what you were trying to get at. If I
flubbed it, please try again.

PS I hope all goes well with you. It seems we've both been lurking in
murky parts of USENET.
--
Jeff Barnett

On Fri, 9 Feb 2024 21:13:18 -0000 (UTC), Spiros Bousbouras wrote:

> (declaim (ftype (function (vector vector list
> &key (:limit (or null integer)) (:so-far
> integer))
> list)
> split-vector))

Not a fan of “parenthesis-pileup” layout. This helps make it clearer
to me:

(declaim
(ftype
(function
(vector vector list &key (:limit (or null integer)) (:so-far integer))
list
)
split-vector
)
)

Jeff Barnett <jbb@notatt.com> writes:

> On 2/13/2024 7:13 AM, Ben Bacarisse wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 2/12/2024 1:53 PM, Ben Bacarisse wrote:
>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>
>>>>> On 2/11/2024 3:38 AM, Ben Bacarisse wrote:
>>>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>>>
>>>>>>> On 2/11/2024 12:00 AM, Alan Bawden wrote:
>>>>>>>> Julieta Shem <jshem@yaxenu.org> writes:
>>>>>>>> Vectors are not convenient when we want to build something one
>>>>>>>> element
>>>>>>>> at a time. I think coercing a list into a vector is O(n), but that
>>>>>>>> seems inevitable because to make a vector we need to know the size and
>>>>>>>> we don't know the size up front.
>>>>>>>> This is why we have arrays with fill pointers. You should read up on
>>>>>>>> how arrays (and vectors) really work, with an eye on eventually being
>>>>>>>> able to use VECTOR-PUSH-EXTEND on a array that's specialized to contain
>>>>>>>> just 8-bit bytes.
>>>>>>>
>>>>>>> N.B. The use of vector-push-extend, where extend happens many (for many
>>>>>>> definitions of "many") times, will consume O(n^2) time AND probably memory
>>>>>>> too. There is no free (or even cheap) lunch when you don't have a good
>>>>>>> estimate of final total size up front.
>>>>>> Is this true for real implementations? I would have thought they would
>>>>>> typically use an exponential allocation strategy to give what is often
>>>>>> called "amortised O(n)" growth.
>>>>>> That is certainly what I found in a quick experiment using clisp:
>>>>>> (defun build-vec (size)
>>>>>> (let ((a (make-array 0 :adjustable t :fill-pointer t)))
>>>>>> (dotimes (i size (length a)) (vector-push-extend i a))))
>>>>>> shows linear growth in execution time.
>>>>>
>>>>> Every time you do a rebuild initiated by a push-extend you end up copying
>>>>> all the current items in the vector;
>>>> Why? Having to copy everything, even in a tight reallocation loop like
>>>> the one I used, will be a problem.
>>>>
>>>>> and each time you do the copy, more
>>>>> items are copied than for the last copy. This leads, finally, to O(n^2)
>>>>> complexity. And as to storage, you must look at all the allocations you
>>>>> have done and the overhead to either GC or tack them into your
>>>>> heap. Usually, you only notice this degradation if you push a whole lot of
>>>>> items - recall, O(.) is really an asymptotic measure. Lots of tricks will
>>>>> hide the problem for a while but one usually gets bit in the end.
>>>>>
>>>>> When you ran build-vec, did you let size be a few billion? What
>>>>> happened to run time?
>>>> No, I could only go up to (expt 2 23) before clisp seg faulted (surely a
>>>> bug?). That's only about 8 million items, but 134 million bytes of
>>>> storage. The time taken was almost perfectly linear.
>>>>
>>>>> My guess is that most storage heap management schemes take about
>>>>> the same amount of time and storage to allocate a few bytes and a few
>>>>> thousand bytes. The growth effect, if it is real in the implementation you
>>>>> are using for testing, must build vectors many many times longer than the
>>>>> internal allocation chunk size to see the quadratic effect.
>>>> Can you post an example? I don't know how to get either clisp or SBCL
>>>> to go much larger. They both have options which would seem to control
>>>> this but I can't seem to get them to cooperate! Any help would be much
>>>> appreciated.
>> ...
>>> I don't know if it will help but I'll tell you a few of the assumptions I
>>> made leading to what I wrote above.
>> Thanks for what you wrote, but I was hoping for some help to extend my
>> tests so I could see the effects you think I should be seeing but which I
>> was not. I saw linear growth up to the point where the implementations
>> crapped out and I could not see how to extend them.
>> By the way, I don't think one can assume that in-place reallocation with
>> an exponential growth strategy in always going to be in place. I was
>> just suggesting that's it's likely to be what is used in some
>> implementations.
>
> I wasn't assuming an in-place reallocation.

Yes, I know. I was just remarking that my own observations that just
because as least two implementation appear to offer amortised O(n) cost,
that result can't be relied upon as the language does not stipulate any
underlying strategy.

> I'm not sure if I understood what you were trying to get at. If I flubbed
> it, please try again.

I was simply reporting the result of a measurement up to the maximum
size I could manage.

--
Ben.