Why does a subtraction operation make this over 100 times slower?

anon20074439 · February 27, 2019, 10:26pm

I’m not sure that is the fix.

If I do

[code]Dim mb As New MemoryBlock(2)
mb.Byte(0) = Bitwise.BitOr(mb.Byte(0), 32)

Dim a, b, c, d As String
Dim points() As Boolean = Array (True, False, False, False, True, False, True, True, False, False, True, False, False, True, True) // 100010110010011

System.DebugLog(“INPUT: 100010110010011”)

'a = EncodedBytesStringFromPointsOLD(points())
b = EncodedBytesStringFromPoints(points())
'c = EncodedInvertedBytesStringFromPointsOLD(points())
'd = EncodedInvertedBytesStringFromPoints(points())

display(a)
display(b)
display©
display(d)

'quit[/code]

I still see a huge drop.

22:23:14 : INPUT: 100010110010011
NEW: 44.05762
22:23:16 : INPUT: 100010110010011
NEW: 12.63672

Even when calling just

a = EncodedBytesStringFromPointsOLD(points())

which doesn’t use bitwise with the dim and bitwise commented out from the top of the button I see a huge speed improvement between the two calls.

Aaron_Hunt · February 27, 2019, 10:33pm

[quote=426468:@]I’m not sure that is the fix.

If I do
…
I still see a huge drop.

NEW: 44.05762
NEW: 12.63672
[/quote]

But that’s not so huge. The numbers you’ve posted for first time calls haven’t been anywhere near those I am seeing. Add 1000 microseconds to the first time and it’s more like what I get. And my second calls have never been as fast as yours. See:

NEW: 1446.086
NEW: 38.18799

anon20074439 · February 27, 2019, 10:38pm

Very odd indeed. I’d throw all this in a feedback ticket and give them all a brain teaser

Aaron_Hunt · February 27, 2019, 10:45pm

The thing is, it turns out to be only 100 milliseconds lost on the first call. So ultimately, who cares?

anon20074439 · February 27, 2019, 10:55pm

gasp

That depends how deep the rabbit hole goes i.e. does it happen every few seconds / calls, only looking into it could find out, those ms could quickly add up.

Daniel_Taylor · February 27, 2019, 11:14pm

I replaced the write bits subsection of EncodedBytesStringFromPoints with the code below. In one-off calls the speed gain can vary from 10-40%. But if I call the two variations in a loop 1,000x each it’s a pretty consistent 30-40% gain. (Compiled 64-bit Mac builds.)

The code below requires the input Points array to have complete octets. Your sample input is missing the first 0. I’m assuming any real world input would consist of complete octets, otherwise you would have to know how to breakup the string and assign ranges of booleans to each byte.

Alternatively if your real world input might skip leading zeros on only the first byte value it would be easy to detect and pad. (Though I guess that raises the question of whether or not padding the string would wipe out the speed gain.)

Here’s the sample input I used. Same as yours but it starts with a zero/false.

dim points() as boolean = Array(false, true, false, false, false, true, false, true, true, false, false, true, false, false, true, true) // 0100010110010011

My goal here was to minimize the MemoryBlock accesses and eliminate the division. Note that I moved the declaration for value to this section.

' write bits
Dim pointStart As Integer = 0
For bytePos = 0 To size Step 1
Dim pointPos As Integer = pointStart + 7
Dim value As UInt64 = 0

For bitPos = 0 To 7 Step 1
If Points(pointPos) = True Then
value = Bitwise.BitOr(value, Pow(2, bitPos))
End If
pointPos = pointPos - 1
Next

mb.Byte(bytePos) = value
pointStart = pointStart + 8
Next

Not sure if you need any additional speed…I was just curious and I thought I would try those changes.

Aaron_Hunt · February 28, 2019, 1:31pm

See above, I already tested for that using a timer set to call at random intervals. It only happens once.

kevin_g · February 28, 2019, 1:38pm

Have you tried replacing the bitwise or:

value = Bitwise.BitOr(value, Pow(2, bitPos))

with:

value = (value Or Pow(2, bitPos))

Aaron_Hunt · February 28, 2019, 1:39pm

Daniel, thanks for the optimisation. The input is a variable length array, so only randomly would it be in octets, but you’ve given me some things to think about here. I am interested in any ways possible to speed it up. I considered writing it in C and calling it as a .dylib but didn’t get very far (the data types in C made things ugly).

EDIT: just an FYI, I tested your code and found that the bit placement in bytes above 0 is off by one. I had trouble following how the values are calculated, so I didn’t try to fix it. Here is the method I use to check the output (not optimised for anything):

Protected Function MBtoString(mb as MemoryBlock) as string dim s as string dim z, j, k as integer dim b as byte z = mb.size-1 for j = 0 to z for k = 7 downto 0 b = pow(2, k) if Bitwise.BitAnd( b, mb.byte(j) ) = b then s = s + "1" else s = s + "0" end if next next return s End Function

kevin_g · February 28, 2019, 1:41pm

Another potential optimisation might be to pre-calculate the Pow(2, bitPos) into an array and then just refer to the array index in the calculation.

Aaron_Hunt · February 28, 2019, 1:43pm

[quote=426534:@Kevin Gale]Have you tried replacing the bitwise or:

value = Bitwise.BitOr(value, Pow(2, bitPos))

with:

value = (value Or Pow(2, bitPos))

No, I had no idea “or” could be used that way in Xojo. The LR says “it is equivalent to calling the BitOr method of the Bitwise class” so it might not make a difference, but I’ll see. Thanks. It’s certainly more readable code in any case! The Bitwise object is ugly compared to other languages.

Very good idea, thanks. I’ll store the powers of 2 in a Global array filled when the app opens and just look up the values.

Daniel_Taylor · March 1, 2019, 2:50am

Regardless of length, wouldn’t it be possible to pad out the first part of the input to fill an octet after which everything else falls into line?

I’m getting identical strings between EncodedBytesStringFromPoints and my version. But, again, I’m only feeding it test arrays that are evenly divisible by 8. If the test array is not divisible by 8 then I’m sure the final result will be off.