String Optimization

[coolcurrent4u]

Hi all, can any one help me optimize this code. cause is make my program slow

For i = LBound(WordsArray) To UBound(WordsArray)
        For j = LBound(CommaArray) To UBound(CommaArray)
            If InStrB(CommaArray(j), WordsArray(i)) <> 0 Then
            k = k + 1
            ReDim Preserve strTemp(1 To k)
            strTemp(k) = CommaArray(j)
            End If
        Next j
    Next i

[MartinLiss]

What are you trying to do? An example in words would help.

[si_the_geek]

Thread moved from CodeBank forum (which is for you to post your code examples, not questions)

The biggest issue there is the use of Redim Preserve (just Redim by itself is slow, and Preserve is even worse!). It doesn't matter how many items you increase it by, but how often you do it - so a common way to optimise this is to increase it by more each time, so you don't have to do it so often.

Here is one way to do that:

Dim lngArrayMax as Long           'extra variable & const for actual array size and growth
Const c_lngGrowBy as Long = 50    '(see note about these two lines after the code)
    lngArrayMax = 200
    ReDim Preserve strTemp(1 To lngArrayMax)  'size the array to our expected minumum

    For i = LBound(WordsArray) To UBound(WordsArray)
        For j = LBound(CommaArray) To UBound(CommaArray)
            If InStrB(CommaArray(j), WordsArray(i)) <> 0 Then
               k = k + 1

               If k > lngArrayMax Then   'only expand the array if needed
                  lngArrayMax = lngArrayMax + c_lngGrowBy
                  ReDim Preserve strTemp(1 To lngArrayMax)
               End If

               strTemp(k) = CommaArray(j)
            End If
        Next j
    Next i

    If k <> lngArrayMax Then  'now it is finished, reduce the size to what was actually used
       ReDim Preserve strTemp(1 To k)
    End If

The best values for c_lngGrowBy and lngArrayMax depends on how big the array is likely to be at the end... the initial value for lngArrayMax should be the minimum you expect, and c_lngGrowBy should be a decent proportion of the gap between minimum and maximum.

The numbers shouldn't be too big, as that will mean you are wasting memory (depending on circumstances, that could slow the computer down dramatically), but shouldn't be too small either (as you will be losing speed from repeatedly Redim'ing).


edit: how slowly did I type this post!

[Merri]

InStrB needs more careful attention than InStr, but if there will always be non-Unicode characters, then it is OK in this case.

As for optimization, you may want to use a zero based array instead, because it is a lot faster than other bases (especially compiled). Another big problem is the constant use of ReDim Preserve: you probably want to call it rarely, so that you don't make computer constantly reserve a new array and copying information there.

'
    lngMaxIndex = 999
    ReDim strTemp(0 To lngMaxIndex)
    For i = LBound(WordsArray) To UBound(WordsArray)
        For j = LBound(CommaArray) To UBound(CommaArray)
            If InStrB(CommaArray(j), WordsArray(i)) <> 0 Then
                ' are we within array bounds?
                If lngMaxIndex < k Then
                    lngMaxIndex = lngMaxIndex + 1000
                    ReDim Preserve strTemp(0 To lngMaxIndex)
                End If
                strTemp(k) = CommaArray(j)
                k = k + 1
            End If
        Next j
    Next i
    If k - 1 < lngMaxIndex Then
        lngMaxIndex = k - 1
        ReDim Preserve strTemp(lngMaxIndex)
    End If

Edit!
Yay, I found this thread just before si_the_geek posted


Edit #2!
Just as an interesting note, k at the end of this code will contain the total number of items while lngMaxIndex contains the UBound.

[Ellis Dee]

Logophobic discovered that one of the best ways to redimension a growing array is to double the size each time. This is both efficient and scalable, so you don't have to tweak it for each different situation.

I like to start with 16 elements just because it seems like a nice balance between quick growth and not wasting too much space for smaller arrays.

Here's a snippet:

' Initializations
lngCurrent = 0
lngMax = 15
ReDim MyArray(lngMax)
 
' Later, inside the loop...
lngCurrent = lngCurrent + 1
If lngCurrent > lngMax Then
    lngMax = (lngMax + 1) * 2 - 1 ' 15, 31, 63, 127, 255, etc...
    ReDim Preserve MyArray(lngMax)
End If
 
' After loop, optional clearing of dead weight
lngMax = lngCurrent
ReDim Preserve MyArray(lngMax)

[Merri]

That may be true for relatively small amount of items, but with large amount of items the extra weight can soon make things slower, although most importantly memory usage is also of concern. Very case dependant... but my point here is valid at least for string builder classes, where doubling the size each time when processing large strings can and will soon lead to serious memory usage issues.

It might be worth investigating the magical 65536 bytes size and what happens after that if array size is still being doubled vs. increasing the size constantly with the same size (be that smaller than 64k or exactly 64k). I don't quite feel like doing that though, so I'm throwing the ball at someone else.

[Ellis Dee]

That may be true for relatively small amount of items, but with large amount of items the extra weight can soon make things slower, although most importantly memory usage is also of concern. Very case dependant... but my point here is valid at least for string builder classes, where doubling the size each time when processing large strings can and will soon lead to serious memory usage issues.

It might be worth investigating the magical 65536 bytes size and what happens after that if array size is still being doubled vs. increasing the size constantly with the same size (be that smaller than 64k or exactly 64k). I don't quite feel like doing that though, so I'm throwing the ball at someone else.

I'm not convinced. I don't quite feel like setting up a benchmark either, but that doesn't mean we can't run some thought experiments.

Give me some examples of growing an array inside a loop that will redimension more efficiently than doubling.

Hmmm, I'm starting to get motivated, but maybe that will pass.

[leinad31]

The doubling your referring to was used to generate repeating characters, e.g.

sample
samplesample
samplesamplesamplesample

Although the number of repetitions were known, the doubling focused on the values rather than the size of the data structure (please note that end target or number of repetitions was already known).

In the case of this thread, as Merri mentioned, doubling would be inefficient when you only need one more but will end up creating hundreds or thousands of additional array elements.

[Ellis Dee]

The doubling your referring to was used to generate repeating characters, e.g.

sample
samplesample
samplesamplesamplesample

No, that's a different thread, and that idea was anhn's, not Logo's.

I'm searching for the array thread where Logo pointed out the doubling technique...

[leinad31]

I imagine it is related to path finding algorithms where the rate of growth of data within processing loop is justifies doubling the array (binary tree data growth). This can be noted by your own code comment "After loop, optional clearing of dead weight".

In the case of usage of thread starter, if he is going to implement something similar to your approach. Then might as well increase array size equivalent to (or a percent of) WordsArray size then trim off the dead weight later. Max number of resizes is then known, e.g. at 10% of WordsArray you'd have max of around 10 redims.

[Merri]

I had my thoughts a bit messed up (I blame the cat), but in general my view on memory usage is correct. When you start small and go on doubling the size, what happens is that on lower indexes you end up calling ReDim far more often than what happens if you start relatively big (like big enough that most often two ReDims is enough).

Say you start off from 16 items and double that and go up to 4096 items.

16 > 32 > 64 > 128 > 256 > 512 > 1024 > 2048 > 4096 = 9 ReDims

If you use a constant size of 1024, you end up with only 4 ReDims. And ReDim is the costly call here. Of course you could ask to go up to million items, but in that case you could use a bigger constant size (the minimum expected size). Yet you could go ahead and use doubling and start from the same minimum size, but when you do that with high number of items, you soon get into the situatation that you're probably reserving much more unused memory space (it is much more likely, because cumulative effect is massive).

Doubling would probably be best suited if you know the data will increase the same way as array size grows, cumulatively, yet you won't know the exact amount of final items. In any other case it is most likely better to use the constant size.

In the end, it is all about how many times you ReDim, because that is the call that costs time, and you don't need a benchmark to detect how many times it has been called. All the other things that happen in the loop are a must-have you can't take away.


Edit!
Also, if you're implementing a class where you're letting user to add items, using doubling would be inefficient memorywise. With constant value you could even let user of the class determine the best value, like user could change the value before adding a lot of items and only one ReDim would happen. With doubling the best you could do would be let the user give a new buffer size, but adding even one more item after exceeding that amount would double the array memory usage (of course we don't account here for what objects or strings might use).

[Ellis Dee]

Edit!
Also, if you're implementing a class where you're letting user to add items, using doubling would be inefficient memorywise. With constant value you could even let user of the class determine the best value, like user could change the value before adding a lot of items and only one ReDim would happen. With doubling the best you could do would be let the user give a new buffer size, but adding even one more item after exceeding that amount would double the array memory usage (of course we don't account here for what objects or strings might use).

We had a thread going complete with benchmark programs, and a side issue arose of what the best buffer size would be depending on the expected number of elements.

Logo offered a throwaway "or you could gain the same speed by just doubling the array each time".

It's driving me crazy that I can't find that thread.

[leinad31]

Try path finding algorithms, or other algorithms that deal with binary trees.

[Merri]

That still skips my point of inefficiency in memory: you are still likely to waste memory more than necessary. I'm not talking as much about speed optimization as I'm talking about memory usage optimization. But all this is relevant only if we're talking about thousands of array elements or more. Speedwise the differences aren't as big, especially with low amount of elements, as long as you're not doing ReDim on every iteration.

[Milk]

I think I would argue the neatest coverall might be to double the size until a cut off (how about the magic 64KB) an then increment the size by that.

It's worth checking the return of VarPtr(Arrayname(0)) after Redim to see if a copy has been made or not, often you see that the array has been able to resize without copying itself elsewhere.

I might just have a look at this later myself.

[Ellis Dee]

That still skips my point of inefficiency in memory: you are still likely to waste memory more than necessary. I'm not talking as much about speed optimization as I'm talking about memory usage optimization. But all this is relevant only if we're talking about thousands of array elements or more. Speedwise the differences aren't as big, especially with low amount of elements, as long as you're not doing ReDim on every iteration.

The waste is never more than 100% of the array itself; think of it like a mergesort, which allocates a second array the same size as the one you're sorting. In this case, since you don't double until you exceed the previous size by one, the maximum waste is 1 element less than 100%.

Now consider the fixed buffer approach. What if the buffer is 64k, and the array size is only 10k? You've wasted 50k, or 500%.

It is worth pointing out that it's not the number of ReDim calls that matters; it's how many elements each call Preserves that matters. The following two snippets will run at noticeably different speeds:

ReDim MyArray(0)
ReDim Preserve MyArray(640000)
ReDim Preserve MyArray(1280000)
ReDim Preserve MyArray(1920000)

ReDim MyArray(0)
ReDim Preserve MyArray(1)
ReDim Preserve MyArray(2)
ReDim Preserve MyArray(1920000)

The first example preserves 192000 more elements than the second one does. This is obviously an extreme example, but the second one only does half the work the first does.

Let's say you have a million elements, and you have a 10k buffer. That's 100 redimensionings, which preserves 10k+20k+30k+40k+...+900k = 50,500,000 elements.

Even if you increase the buffer size to 100k, that still leaves 10 dimensionings preserving 5,500,000 elements.

To grow a million elements by doubling, using the arbitrary starting point of 15 (16 elements including 0), you only need 16 dimensionings preserving 2,097,104 elements. Much, much faster.

I'll spend enough memory to double the starting array size for speed gains like that.

[Ellis Dee]

I'd be interested in other growth patterns, but doubling feels like the best bet.

A more conservative approach memory-wise but still with decent runtimes might be the Fibonacci sequence.

If you have no idea how many elements you're going to get, a fixed buffer is a poor approach indeed. If you do know (even roughly) how many you're going to get, you shouldn't be calling ReDim Preserve at all; you should allocate as much as you need up front.

I'm having trouble thinking up a scenario where a fixed buffer approach is a good idea.

[leinad31]

You don;t have to guess nor double, WordsArray size can lead to a good estimate as it represents the worst case scenario.

[Ellis Dee]

You don;t have to guess nor double, WordsArray size can lead to a good estimate as it represents the worst case scenario.

Exactly, so in this case there shouldn't be any redimensioning inside the loop at all.

I found the thread I was talking about; it was from August of last year.

EDIT: I don't see where he mentions doubling. Must be a different thread.

[Ellis Dee]

I found the thread I was talking about; it was from August of last year.

EDIT: I don't see where he mentions doubling. Must be a different thread.

And I finally found his offhand remark. Two days after that thread, he mentions the doubling idea in passing in this thread.

As you can see by my followups to his post, the idea resonated with me. Benchmarking goodness soon followed. And I see anhn shows up at the end of the thread, days after he joined the boards. Maybe that was the seed of his string concatenation solution from last month.

[Merri]

Give me some examples of growing an array inside a loop that will redimension more efficiently than doubling.

I chose a small range of 8192 items, because one rarely goes higher than that in every day use, and it also makes up that magical 65536 bytes in memory.

Command1 = double
Command2 = one fourth
Command3 = fixed size (in this test one eight of maximum)

Compile with all advanced optimizations because math is involved.

Option Explicit

Private Sub Command1_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long
    Dim TestArray() As Long
    Start = Timer
    For lngB = 1 To 10000
        ReDim TestArray(1)
        For lngA = 1 To 8192
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld)
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) * 2)
            End If
        Next lngA
    Next lngB
    Command1.Caption = Format$(Timer - Start, "0.000000") & " - " & lngCopyCount & " - " & UBound(TestArray)
End Sub

Private Sub Command2_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long
    Dim TestArray() As Long
    Start = Timer
    For lngB = 1 To 10000
        ReDim TestArray(4)
        For lngA = 1 To 8192
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld)
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) + UBound(TestArray) \ 4)
            End If
        Next lngA
    Next lngB
    Command2.Caption = Format$(Timer - Start, "0.000000") & " - " & lngCopyCount & " - " & UBound(TestArray)
End Sub

Private Sub Command3_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long
    Dim TestArray() As Long
    Start = Timer
    For lngB = 1 To 10000
        ReDim TestArray(0)
        For lngA = 1 To 8192
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld)
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) + 1024)
            End If
        Next lngA
    Next lngB
    Command3.Caption = Format$(Timer - Start, "0.000000") & " - " & lngCopyCount & " - " & UBound(TestArray)
End Sub

All I can say is that you must run the executable many times, because it seems there are "sweet spots", when one code works much better than usual.

My latest run gave this kind of results:
0,687500 - 20000 - 8192
0,765625 - 30000 - 8282
0,625000 - 20000 - 8192

The first value is time, the second value tells how many times the array was ReDimmed during the entire test and last value is the total number of items in the array after being finished.

One could say fixed size is the fastest, but as hinted earlier this isn't the entire story. The "worst case" results are like this, when the app seems to get a "bad spot" in memory:

1,281250 - 70256 - 8192
1,421875 - 69999 - 8282
1,343750 - 50000 - 8192

As you can see, in a bad spot the array gets copied far more often. While making the test I ended up with one fourth as it seemed to be much faster. Then as I tested more, I started to get more often always either the best case or always the worst case. However, the one fourth code seemed to, at first click on it, to work as if it was in a good spot even when the results after the first run were all bad spot results.

I don't know what kind of results you'll get, but these should be pretty interesting. As you can see, I didn't bother with a high performance timer.

[leinad31]

Memory paging.

[Ellis Dee]

The buffer you tested is exactly 25% of the final size. That's hardly a reasonable simulation of buffering an unknown number of elements.

Refer to this post to see the dramatic performance differences when you don't happen to pick an ideal buffer size.

[Merri]

You're welcome to test a bigger amount of items: I tested it with 15 times bigger values and it kept going just as fast (and got an advantage actually as the size wasn't having as many unrequired items).

1024 / 8192 * 100 = 12,5%

Although I do think the size of 1024 is the important factor here, 8 kB. You can also make that double and it performs pretty much the same, but going bigger starts degrading performance. We have actually had some discussion about this earlier sometime. Also, when you go to really big array sizes it does lose it's speed (probably runs out of some buffering so doubling/half add/quarter add gets an advantage).

[Ellis Dee]

1024 / 8192 * 100 = 12,5%

Uh...oops? hehheh.

[Merri]

Here is one that makes random values between 0 and 102400 and then benchmarks and also shows how many bytes were copied:

Option Explicit

Private Const MAXVALUE = 1024 '81920
Private Const ITERATIONS = 1000

Private Sub Command1_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long, lngSize As Long
    Dim TestArray() As Long
    Randomize 1
    Start = Timer
    For lngB = 1 To ITERATIONS
        ReDim TestArray(1)
        lngSize = 4
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) * 2)
                lngSize = lngSize * 2
            End If
        Next lngA
    Next lngB
    Command1.Caption = Format$(Timer - Start, "0.000000") & " - " & FormatNumber(lngCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes"
End Sub

Private Sub Command2_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long, lngSize As Long
    Dim TestArray() As Long
    Randomize 1
    Start = Timer
    For lngB = 1 To ITERATIONS
        ReDim TestArray(4)
        lngSize = 16
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) + UBound(TestArray) \ 4)
                lngSize = lngSize + lngSize \ 4
            End If
        Next lngA
    Next lngB
    Command2.Caption = Format$(Timer - Start, "0.000000") & " - " & FormatNumber(lngCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes"
End Sub

Private Sub Command3_Click()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, lngCopyCount As Long, lngSize As Long
    Dim TestArray() As Long
    Randomize 1
    Start = Timer
    For lngB = 1 To ITERATIONS
        ReDim TestArray(0)
        lngSize = 0
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                lngCopyCount = lngCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                ReDim Preserve TestArray(UBound(TestArray) + 2048)
                lngSize = lngSize + 2048
            End If
        Next lngA
    Next lngB
    Command3.Caption = Format$(Timer - Start, "0.000000") & " - " & FormatNumber(lngCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes"
End Sub

As you can see when you test it, you are correct in that doubling size copies a lot of stuff faster, but the problem is that with random amount of items ranging from 0 to 102400 it just has too bad worst cases to actually drop the total performance (I guess doing exactly the opposite of what you were expecting from random amount of items?). Fixed size remains faster in general. At least, I kept getting about 0,9 while double was most often in the 1,0 - 1,1 range, randomly going as far down as 0,6.

However, the one fourth seems to show it's fangs here and is sometimes very very fast, having far more often good cases than worst. It often ran in the 0,4 - 0,9 range. So I guess that'd be my suggestion instead of double and instead of fixed size. You're welcome to test further, I guess I've had enough of this massive offtopic Been up well over 20 hours so I'm not too sharp either.

[Ellis Dee]

On my machine the results I get when first run are (rounded off):

Double: 0.52
Quarter: 0.39
Fixed: 0.66

All three climb steadily if I keep running it. The quarter progression looks quite impressive. I wonder how the Fibonacci sequence, or the magical 1.3 progression CombSort uses would work.

ETA: You didn't seed Rnd with a negative value before calling Randomize, so the random sequences weren't repeating.

[Ellis Dee]

I implemented some bugfixes and added the Fibonacci sequence as well as combsort's "magical 1.3" progression. EDIT: I also added a random seed, so that each test will run a different sequence.

Option Explicit

Private Const MAXVALUE = 1024 '81920
Private Const ITERATIONS = 1000

Private mlngSeed As Long

Private Sub Doubling()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, curCopyCount As Currency, lngSize As Long
    Dim TestArray() As Long
    Rnd -1
    Randomize mlngSeed
    Start = Timer
    For lngB = 1 To ITERATIONS
        lngSize = 15
        ReDim TestArray(lngSize)
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                curCopyCount = curCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                lngSize = (lngSize + 1) * 2 - 1
                ReDim Preserve TestArray(lngSize)
            End If
        Next lngA
    Next lngB
    Text1.Text = Text1.Text & "Double   : " & Format$(Timer - Start, "0.000000") & " - " & FormatNumber(curCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes" & vbNewLine
End Sub

Private Sub Quarter()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, curCopyCount As Currency, lngSize As Long
    Dim TestArray() As Long
    Rnd -1
    Randomize mlngSeed
    Start = Timer
    For lngB = 1 To ITERATIONS
        lngSize = 15
        ReDim TestArray(lngSize)
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                curCopyCount = curCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                lngSize = lngSize + (lngSize + 1) \ 4
                ReDim Preserve TestArray(lngSize)
            End If
        Next lngA
    Next lngB
    Text1.Text = Text1.Text & "Quarter  : " & Format$(Timer - Start, "0.000000") & " - " & FormatNumber(curCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes" & vbNewLine
End Sub

Private Sub Fixed2048()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, curCopyCount As Currency, lngSize As Long
    Dim TestArray() As Long
    Rnd -1
    Randomize mlngSeed
    Start = Timer
    For lngB = 1 To ITERATIONS
        lngSize = 2047
        ReDim TestArray(lngSize)
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                curCopyCount = curCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                lngSize = lngSize + 2048
                ReDim Preserve TestArray(lngSize)
            End If
        Next lngA
    Next lngB
    Text1.Text = Text1.Text & "Fixed2048: " & Format$(Timer - Start, "0.000000") & " - " & FormatNumber(curCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes" & vbNewLine
End Sub

Private Sub Magic13()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, curCopyCount As Currency, lngSize As Long
    Dim TestArray() As Long
    Rnd -1
    Randomize mlngSeed
    Start = Timer
    For lngB = 1 To ITERATIONS
        lngSize = 15
        ReDim TestArray(lngSize)
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                curCopyCount = curCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                lngSize = lngSize + (lngSize + 1) * 1.3
                ReDim Preserve TestArray(lngSize)
            End If
        Next lngA
    Next lngB
    Text1.Text = Text1.Text & "Magic 1.3: " & Format$(Timer - Start, "0.000000") & " - " & FormatNumber(curCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes" & vbNewLine
End Sub

Private Sub Fibonacci()
    Dim Start As Single, lngA As Long, lngB As Long, lngPtr As Long, lngOld As Long, curCopyCount As Currency, lngSize As Long
    Dim TestArray() As Long
    
    Dim lngCurrent As Long, lngPrevious As Long
    
    Rnd -1
    Randomize mlngSeed
    Start = Timer
    For lngB = 1 To ITERATIONS
        lngCurrent = 7: lngPrevious = 4
        lngSize = lngCurrent
        ReDim TestArray(lngSize)
        For lngA = 1 To MAXVALUE * (Rnd * 100)
            If UBound(TestArray) < lngA Then
                lngPtr = VarPtr(TestArray(0))
                curCopyCount = curCopyCount - (lngPtr <> lngOld) * lngSize
                lngOld = lngPtr
                lngSize = lngCurrent + lngPrevious + 1
                lngPrevious = lngCurrent
                lngCurrent = lngSize
               ReDim Preserve TestArray(lngSize)
            End If
        Next lngA
    Next lngB
    Text1.Text = Text1.Text & "Fibonacci: " & Format$(Timer - Start, "0.000000") & " - " & FormatNumber(curCopyCount, 0, vbTrue, vbFalse, vbTrue) & " bytes" & vbNewLine
End Sub

Private Sub Command1_Click()
    Text1.Text = ""
    Fixed2048
    Quarter
    Magic13
    Fibonacci
    Doubling
End Sub

Private Sub Form_Load()
    Randomize
    mlngSeed = Int(65535 * Rnd)
End Sub

My results are consistently:

Fixed2048: 0.781982 - 117,143,765 bytes
Quarter  : 0.406006 -  10,470,818 bytes
Magic 1.3: 0.531006 -  43,483,820 bytes
Fibonacci: 0.437988 -  66,648,912 bytes
Double   : 0.515137 -  46,310,833 bytes

[Merri]

I don't see much wrong in the results, since you're doing initial ReDim with lngSize on consecutive iterations, meaning the starting size on each iteration is different, and you end up timing ReDim instead of ReDim Preserve Also, in my example lngSize contained the number of bytes, now you're using it for number of items, but since the array is a Long array the number of bytes is four times that.

[leinad31]

Any benchmark would lean towards larger array sizes since your testing performance of own code... the real issue is implementing a design that assumes exclusive use of shared resources...what suffers are other running applications, of course you won't be able to benchmark those easily.

Because of dual processors and large memory nowadays, programmers are no longer as conscious of this and as considerate when designing their applications unlike in the old days.

[Ellis Dee]

I don't see much wrong in the results, since you're doing initial ReDim with lngSize on consecutive iterations, meaning the starting size on each iteration is different, and you end up timing ReDim instead of ReDim Preserve

Yeah, that's the problem. All the others reset lngSize, while the Fibonacci one just let it grow. I've corrected and updated the code/results above.

[Ellis Dee]

As you can see when you test it, you are correct in that doubling size copies a lot of stuff faster, but the problem is that with random amount of items ranging from 0 to 102400 it just has too bad worst cases to actually drop the total performance (I guess doing exactly the opposite of what you were expecting from random amount of items?). Fixed size remains faster in general.

This is untrue. Doubling is faster than the fixed-buffer at any size significantly larger than the buffer. Using a fixed buffer approach relies on selecting a good buffer size, which is very call-specific and thus not a good general solution.

While it appears that any progression will do, doubling isn't a terrible option. None of the arguments against have convinced me. First, it was "on large arrays it will be slow and waste memory". Well, it turns out to not be slow, but rather significantly faster than the fixed-biffer approach. As for wasting memory, isn't this the age of computers having gigabytes of memory? How much waste are we talking? A few megabyte for a couple seconds? Totally worth it.

I'll concede that the quarters and Fibonacci progressions are better, in that they seem to be even faster and less wasteful. But you'l have to bring the hard sell to convince me that a fixed-buffer approach is better than any progressive approach.

[leinad31]

Sorry but IMO its better to optimize the entire process rather than optimizing one procedure. If what thread starter is trying to accomplish is similar to dictionary lookup performed by MS Word, even with GBs of memory simply loading everything (e.g. entire webster's) into one gigantic array isn't the best approach.

[Ellis Dee]

Sorry but IMO its better to optimize the entire process rather than optimizing one procedure. If what thread starter is trying to accomplish is similar to dictionary lookup performed by MS Word, even with GBs of memory simply loading everything (e.g. entire webster's) into one gigantic array isn't the best approach.

We are in agreement that the OP should be declaring a large enough array outside the loop so that no redimming is needed. Obviously the discussion of the best way to grow an array inside a loop doesn't apply to the OP; it is a tangent.

But by all means, I agree with your strawman. Don't load all of Webster's into one gigantic array to do a Word-style dictionary lookup. What that has to do with anything is beyond me, though.

[leinad31]

It means he may have to consider re structuring how he stores data, e.g. tokens for partial matches, grouping of data, off-loading to secondary storage, etc, rather than looking for a one size fits all optimization of his procedure. Look at the process and requirements first before assuming problem is entirely in the procedure.

[Ellis Dee]

In that case, when you wrote "Sorry but IMO its better to...", who were you talking to? Because your clarification demonstrates that your response has absolutely nothing to do with what I've been discussing, yet it appeared to be addressed to me and trying to refute what I wrote.

[leinad31]

In that case, when you wrote "Sorry but IMO its better to...", who were you talking to? Because your clarification demonstrates that your response has absolutely nothing to do with what I've been discussing, yet it appeared to be addressed to me and trying to refute what I wrote.

Of course it will have no relevance if you choose it interpret it as such. It was in reply to what was raised... I really couldn't care less who raised it.

[Ellis Dee]

So leinad, tell me, what is the best way to grow an array inside a loop?

[si_the_geek]

You have shown what works fastest for you, based on what is presumably a fairly decent spec PC not doing much else at the time... unfortunately the real usage isn't always like that.

I suspect you have a plenty of RAM available, but not every computer does - lots of people run fairly close the limit, even with brand new PC's (it is shocking how many pc makers still skimp on RAM, and then pre-install lots of memory hungry software ).

While your timings showed that the fixed size was the slowest (but by a usable amount), the careful use of memory means that in a situation where there is a limited amount of RAM available, it could easily become dramatically faster than the other methods (if virtual memory kicks in later than with the others, or not at all).


Unfortunately this is an area where the "best" method is case specific, depending on the amount of memory needed (which we don't know yet, all we know is that it involves strings), and the amount that is likely to be available.

There are several valid options here for coolcurrent4u to try, which should all be noticeably faster than the original... and of course if wanted we can help to optimise/re-design the routine as a whole too (maybe involving a replacement of this loop), which could possibly yield much bigger gains.

I think the best thing to do is wait for coolcurrent4u to comment on what has been suggested so far.

[leinad31]

So leinad, tell me, what is the best way to grow an array inside a loop?

Your staring at the tree and not looking at the woods. Until the thread starter explains more, he will have to satisfy himself with what was already suggested.

For your reference:
http://www.google.com.ph/search?hl=t...Maghanap&meta=