loop performance

madru

Hi Garry,

I've hit a performance wall and would like to share measurements and two requests.

1) Observation: every loop iteration costs about 25 µs

A query whose SQL runs in 25 ms on the server takes about 3.6 s end to end in Objo. The server response is only 1,560 bytes compressed / 7,691 bytes raw. Timing breakdown:

inflate (pure Objo DEFLATE decoder) 2,889 ms
Adler-32 over 7,691 bytes 289 ms
deserialize 7,691 bytes 532 ms

To find the cause I benchmarked individual operations:

Sub BenchPrimitives()
  Var sizes() As Integer = [1000, 2000, 4000, 8000]
  For Each n As Integer In sizes
    Var mb As New MemoryBlock(n)
    Var arr() As Integer
    Var x As Integer = 0
    Var t0 As Double = System.TicksMilliseconds
    For i As Integer = 0 To n - 1
      x = x + mb.ReadByte(i)
    Next i
    Var t1 As Double = System.TicksMilliseconds
    For i As Integer = 0 To n - 1
      mb.WriteByte(i, 7)
    Next i
    Var t2 As Double = System.TicksMilliseconds
    For i As Integer = 0 To n - 1
      arr.Append(i)
    Next i
    Var t3 As Double = System.TicksMilliseconds
    For i As Integer = 0 To n - 1
      x = x + arr[i]
    Next i
    Var t4 As Double = System.TicksMilliseconds
    For i As Integer = 0 To n - 1
      x = x + (i Mod 7)
    Next i
    Var t5 As Double = System.TicksMilliseconds
    Print(n.ToString() + ": ReadByte " + (t1 - t0).ToString("F1") _
      + " | WriteByte " + (t2 - t1).ToString("F1") _
      + " | Append " + (t3 - t2).ToString("F1") _
      + " | arr[i] " + (t4 - t3).ToString("F1") _
      + " | Mod " + (t5 - t4).ToString("F1") + " ms")
  Next n
End Sub

Results (ms):

n ReadByte WriteByte Append arr Mod
1000 77.4 40.1 38.6 36.6 40.6
2000 72.3 72.3 78.2 66.0 51.2
4000 101.0 101.0 100.8 101.8 102.1
8000 201.6 201.4 201.5 203.1 203.7

Everything scales linearly, but every column costs the same ₂₅ µs per iteration regardless of the operation - even a plain x = x + (i Mod 7). That suggests the cost is per-iteration/per-statement overhead rather than in the operations themselves (roughly 40,000 loop iterations per second).

An empty loop For i As Integer = 0 To 7999 : Next i takes 27 ms (about 3.4 µs per iteration), so the loop itself is cheap. Adding a single statement to the body raises it to ₂₀₀ ms, meaning each statement costs roughly 22 µs regardless of what it does. That looks like a fixed per-statement overhead, possibly debugger line tracking.

Is this expected, or could something like debugger instrumentation or event pumping be running on every loop iteration?

2) Request: native zlib / DEFLATE compression

B4XSerializator wraps every payload in a zlib stream (java.util.zip.DeflaterOutputStream format: RFC 1950 container around RFC 1951 DEFLATE). Since Objo has no compression API, I implemented zlib in pure Objo (a port of zlib's puff.c plus Adler-32). It is correct, but at current loop speed it is the dominant cost: 3.2 s for 7.7 KB.

What would help, ideally as shared methods on a Compression class or on MemoryBlock:

  Compression.ZlibCompress(data As MemoryBlock) As MemoryBlock     # RFC 1950 (78 xx header, Adler-32 trailer)
  Compression.ZlibDecompress(data As MemoryBlock) As MemoryBlock
  Compression.DeflateCompress / DeflateDecompress                  # raw RFC 1951, no header
  Compression.GZipCompress / GZipDecompress                        # RFC 1952, for files and HTTP

An optional compression level on the compress side would be nice but isn't essential. .NET's ZLibStream / DeflateStream / GZipStream cover all three directly.

3) Request: bulk MemoryBlock operations

With ₂₅ µs per iteration, any byte-by-byte loop is expensive, so native bulk operations would make a large difference. The ones I miss most:

  mb.CopyBytes(source As MemoryBlock, sourceOffset As Integer, destOffset As Integer, count As Integer)
  mb.Mid(offset As Integer, length As Integer) As MemoryBlock      # or Slice
  mb.ToText(offset As Integer, length As Integer) As String        # UTF-8 decode of a range
  mb.Resize(newSize As Integer)                                    # keep contents
  mb.IndexOf(value As Integer, startAt As Integer) As Integer

If any of these already exist under other names, a pointer would be great and I'll switch to them straight away.

Happy to send the complete project (pure Objo zlib, B4XSerializator, jRDC client) as a test case - it also makes a decent stress test for the VM. Thanks for looking into it!

Best regards,
Guido

bgrommes

madru If any of these already exist under other names, a pointer would be great and I'll switch to them straight away.

I think the following will replace CopyBytes() and Mid():

# Instance method, not shared
sourceMemoryBlock.CopyTo(destinationMemoryBlock,sourceStart,Length,destinationStart)

And this should replace ToText():

# this one is shared, not instance
Var textByes As MemoryBlock = MemoryBlock.FromText(string[,encoding])

I think FromText() is the better design since you can't assume 1 char = 1 byte even in UTF-8 (in theory each character in the string could be 4 bytes if you're outside the BMP, but more commonly, any character outside the ASCII range is at least 2 bytes). Consequently you can't know how big of a MemoryBlock is needed until you decode the string. FromText() takes care of that for you and hands you back the size of block that's needed.

To my knowledge there isn't a Resize, although of course you can do that yourself with CopyTo(). I agree that Resize() would be nice though, as it would likely be faster than the Objo Basic equivalent. I have a use case coming up for that myself.

Regarding your timings, it's not clear to me: are these timing a debug or release build?

Garry

Hi Guido,

I’ve investigated the loop timings. They do not look like a normal 25 µs cost for every Objo statement. In a local run of your benchmark on my MacBook Pro, the 8,000-iteration Mod section took about 1–3 ms without watchpoints. With four enabled debugger watchpoints, it rose to about 176 ms, close to your reported 204 ms. Watchpoints are evaluated as execution reaches new source lines, which would also explain why the different operations have such similar timings.

Could you repeat the test with all watchpoints disabled, then in a built application if possible? Studio’s Run command attaches the debugger, so Run alone does not rule out watchpoint overhead. Please include your Studio version and OS. I can’t yet say watchpoints caused your result; if the built application is still this slow, I’d like the complete project to investigate further.

On zlib: I’ve opened a feature request for in-memory zlib, raw DEFLATE, and gzip compression and decompression. It covers MemoryBlock input and output in both directions, including the zlib format needed for your Java protocol. Native compression is useful regardless of what we find about the loop timings.

For your bulk-operation requests, MemoryBlock.CopyTo() and Slice() already exist. To decode a range as UTF-8, you can use mb.Slice(offset, length).ToText(TextEncoding.UTF8). A correction to the earlier reply: FromText() converts text to bytes; ToText() converts bytes to text. Resize() and IndexOf() are not currently available.

Garry

This feature will now land in the next release (not today's release, the next one!).