Re: Magnitude of Order "For Loop" performance deltas based on syntax change

[Dan Douglas]

On Mon, Sep 26, 2016 at 3:32 PM, Chet Ramey  wrote:
> So you want offset N to be the nth element in the array instead of the >
element with index N? Huh.

Maybe, not always. Both would be nice. The offset isn't the element with
the index N. It's the next set element whose index is >= that of the
selected offset. There's no simple way of knowing how many set elements
come before or after offset - possibly zero. In order to insert something
after the first element you have to find the index of the first element.

> Well, you probably want another data structure.

Yes please. Everybody wants more data structures. (I know... patches
accepted.)

Re: Magnitude of Order "For Loop" performance deltas based on syntax change

[Chet Ramey]

On 9/26/16 11:47 AM, Dan Douglas wrote:
> Would an array of pointers to structs of key-value pairs be better
> here? It should be faster in the common cases even though it may mean
> some wasted space and reallocs depending on how you decide to grow the
> array. A linear search through an array for an index should be faster
> than linked-list traversal. https://youtu.be/YQs6IC-vgmo (why every
> std::vector implementation uses arrays, really it's true of analogues
> in most non-functional langs).

I made a change that makes for-loop 2 nearly twice as fast as for-loop 1,
mostly because it avoids storing and retrieving variables.

> 
> Also bash itself makes it hard to use sparse arrays efficiently regardless
> of the implementation. In the case of lists, one usually wants to address
> elements by ordinal position, but both the index in `arr[index]` and the
> offset in `${arr[@]:offset:length}` don't allow it, which means random
> insertion requires a linear search despite being linked-lists. That also
> makes the "length" inconsistent with everything else that looks at the
> value of the index, though at least length does what I really wish
> offset did.

So you want offset N to be the nth element in the array instead of the
element with index N? Huh.  Well, you probably want another data structure.

In any event, random insertion can be optimized in the same way that
random access is.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRUc...@case.eduhttp://cnswww.cns.cwru.edu/~chet/

Re: Magnitude of Order "For Loop" performance deltas based on syntax change

[Dan Douglas]

Would an array of pointers to structs of key-value pairs be better
here? It should be faster in the common cases even though it may mean
some wasted space and reallocs depending on how you decide to grow the
array. A linear search through an array for an index should be faster
than linked-list traversal. https://youtu.be/YQs6IC-vgmo (why every
std::vector implementation uses arrays, really it's true of analogues
in most non-functional langs).

Also bash itself makes it hard to use sparse arrays efficiently regardless
of the implementation. In the case of lists, one usually wants to address
elements by ordinal position, but both the index in `arr[index]` and the
offset in `${arr[@]:offset:length}` don't allow it, which means random
insertion requires a linear search despite being linked-lists. That also
makes the "length" inconsistent with everything else that looks at the
value of the index, though at least length does what I really wish
offset did.

On top of that, ${!arr[@]:offset:len} doesn't even work. None of the
parameter expansions work with ${!arr[@]}, so to calculate an ordinal
index, a second array containing the indexes of the first is needed. Plus,
pre-existing items are overwritten on assignment, so insertion means
having to save and restore all the indexes and values at least in a
region being inserted to, which means more index calculation.

Re: bash history with mixed timestamps slow and broken

[Eric Blake]

On 09/25/2016 05:39 PM, Chet Ramey wrote:

>> Description:
>>  If the history file (`.bash_history`) starts with a timestamp
>>  (`HIST_TIMESTAMP_START`), and contains lines that have been written
>>  without timestamps, then reading the history file is (a) very slow
>>  because (b) consecutive lines without timestamps are merged into a
>>  single history entry with quadratic complexity.
>>

> 
> The appending behavior isn't really quadratic: the code simply keeps
> reallocating the line and appending to it.  You can imagine how long it
> takes to append a million commands to a single buffer.  You've managed
> to identify the most degenerate case.

That depends on how you do reallocation.

Let's try a simple example: lets say you are processing a list of 128
items.  If you allocate 1 additional slot on each iteration through the
loop, you are performing 128 allocations [O(n)], but you are ALSO
performing 128*127/2 moves [8128, O(n^2)] as you copy the previous
iteration's contents into the newly-allocated larger array.  THAT is
where the quadratic behavior comes from - using a constant-size
allocation pattern requires a quadratic-size copying.

But if instead switch things to do geometric allocation, you amortize
the costs.  On the first iteration, you allocate 1 row.  On the second
iteration, you allocate 2 additional rows (twice the allocation size as
last time), giving you the third iteration free.  On the fourth
iteration, you allocate 4 additional rows (again, double the allocation
size), giving you three more iterations free.  Overall, you perform only
8 allocations [O(log n)], and only 127 moves [O(n)].

As the array sizes get larger, the effects get more pronounced.
Appending a million commands to a buffer absolutely needs geometric
allocation size growth when you reallocate the array, rather than a
constant growth factor, or you quickly become bogged down in the
processing time required to copy the contents on each iteration that has
to reallocate.  ANY good allocation algorithm, where the size of the
list is not known a priori, will use a geometric allocation growth
mechanism (doubling the allocation size is easiest, but a 3/2 growth
ratio also works; the point is that each growth is larger than the last,
so that you get progressively more iterations where you don't have to
reallocate and copy).

-- 
Eric Blake   eblake redhat com+1-919-301-3266
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature