Not a data structure, but a nice concept for very fast search on immutable pre sorted array, eytzinger order. I did some experiments, it is about 2-3x faster then binary search. https://medium.com/swlh/binary-search-vs-eytzinger-order-301...

If you need a language support for FlexBuffers please create an issue on GitHub repo. I ported it already to Swift, C#, Dart, Python, JS (is in review). If I am familiar with the language you need, it will take me just a couple of days to port it.

One use case where schema-less is the way to go, when you provide the infrastructure, but have no „ownership“ of data it will be used for. E.g. you build a logging or analytics tool where customers can send arbitrary data. Or a document database as a matter of fact. There schema-less / self described data is a must.

Not necessarily. For logging/analytics, you could have customers upload their schema when configuring the service. I would think that doing so would allow for some powerful optimization opportunities, enabling your service to save quite a bit of CPU and maybe some bandwidth, too. It would probably also allow you to provide a better user experience, like making it easier to construct dashboards and such because you actually know how the data is structured.

For a document database, I don't agree at all. Some time back I spent more time than I'd like developing on Mongo, and boy did I wish I could actually tell it the schema of documents in each collection and have it enforce that (not to mention optimize based on it). A lot of developers actually use libraries on top of Mongo to define and enforce schemas.

You can apply a Schema to your collection and have MongoDB enforce it . This has been in MongoDB since version 3.6. We support the JSON schema standard. https://docs.mongodb.com/manual/core/schema-validation/

Cool! My time using Mongo was pre-3.6 so I didn't know about this.

True, I guess it all boils down to ease of use (convenience). You can build a system which accepts schema + data and build dash boards and data relevant relevant processing + optimisations, but that results in a much more complex system with higher entry burden. Sadly convenient systems always get broader adoption.

Yeah, I see this as pretty similar to the debate over type-safe vs. dynamic languages. It used to be that people argued that dynamic languages were just way easier to use, and type-safe languages were just an optimization. But I think the real issue was that the tooling enabled by type-safe languages didn't exist yet. These days, TypeScript is no faster than JavaScript but is very popular, because of the tooling it enables, like editors with auto-complete and jump-to-definition.

I think protocols still don't have the level of tooling that makes it really obvious why schemas are better.

I own a service where users simply upload their schemas along their data. Doesn't seem to be a major issue.

You forgot Python and C# :). Plus a Unity3D specific version, which is battle tested in a game with more than half a million downloads ;).

The good thing about any narrative, it resonates with different people on different levels.

The blog post is in deed titled "10,000 times faster Swift". I though it will be a catchy title even though 6 seconds to 0.35 ms is not factor of 10,000.

I thought about renaming the title to 500 times faster Swift, which would be rathe more accurate insight of current findings, but than what the hack. It's a blog post. I didn't published a scientific paper. I just reflected on my resent work.

The main points of the Blog posts wehere anyways about how it is possible to make low level optimisations to make Swift programs faster. And as a matter of fact the Loop-invariant code motion was a valid technique to get the same result. Result being sum of payload content. The compiler was smarter than me. It gave me the same result doing 250times less work. I find it impressive.

I must be honest I am not fluent in assembly this is why I could not figure it out by myself.

Was I suspicious? Absolutely!!! But the facts were in my face.

Shouldn't I publish an article, where I am not sure why I got what I got? If I wouldn't publish the article, I would not figured out the truth and wouldn't learned form this experience.

And after all, this post is about performance pitfalls in Swift language. The comparison with C was almost accidental. I would compare it with C++ if I would have a Windows machine, as the benchmark for C++ project has Windows specific code. I also consulted with the author of flatcc, who is much more relaxed about my blog post than you are :)

This blog post is about learning something. I learned something before I wrote this post I shared it and now I learned even more.

You should try it yourself.

Maybe not as satisfying as criticising, but it also has it's moments.

I Updated the run bench function

https://gist.github.com/mzaks/e3a2dc7ccdfc2397bc26c55eb6dc8a...

the output is now:

  Eager run
  =================================
  1557 ms encode
  264 ms decode
  34 ms use
  206 ms dealloc
  504 ms decode+use+dealloc
  0,38 ms direct
  0,32 ms using struct
  =================================
  Total counter1 is 8644311667000000
  Total counter2 is 8644311667000000
  Total counter3 is 8644311667000000
  Encoded size is 315 bytes, should be 344 if not using unique strings
  =================================

As you can see all three counters are equal.

The function call is not being optimized out, it's being hoisted outside the loop. I.e., it is as if the code was written as:

    let result = flatuseStruct(outputData)
    for _ in 0..<iterations {
        assert(result == 8644311667)
        total = total + UInt64(result)
    }

The counter will still be correct, but you are not measuring what you think you are measuring.

This makes sense!

Changed the iteration to:

   for i in 0..<iterations {
     let result = flatuseStruct(outputData, start:i)
     assert(result == 8644311666 + Int(i))
     total2 = total2 + UInt64(result)
   }

now result is around 43ms

Thanks for pointing it out. Have to check if there are so other things involved, but that might be it.

That's 0.35 nanoseconds to do something.

If it is a nop on a modern cpu it can run x4 nops at the same time. Either you aren't doing useful work or your measurements are wrong.

Unfortunately I can't view gists in work.

You can see the problem here:

First it cals CFAbsoluteTimeGetCurrent and saves the result.

    0x100272dab <+10443>: callq  0x1002b7b38 ; CFAbsoluteTimeGetCurrent
    0x100272db0 <+10448>: movapd %xmm0, -0xa0(%rbp)

Here is the call to flatDecodeDirect. I guess RDI is the input. That's usual for the x64 ABI.

    0x100272db8 <+10456>: movq   -0x100(%rbp), %rdi
    0x100272dbf <+10463>: callq  0x10026fb10 ; flatDecodeDirect

I don't know what this next bit is for.

    0x100272dc4 <+10468>: testq  %rax, %rax
    0x100272dc7 <+10471>: js     0x10027444c ; <+16236> [inlined] generic specialization <FlatBuffersPerformanceTestDesktop.FlatBufferReader> of Swift._ContiguousArrayBuffer._checkValidSubscript (Swift.Int) -> ()

0x3e8=1000. The loop counter is in ECX.

    0x100272dcd <+10477>: movl   $0x3e8, %ecx

I can't figure out what's at these two addresses; lldb didn't seem to accept any reasonable syntax. lldb is terrible. But I'll bet that RBX is holding the value of `total'. I don't know what r14 is, and it doesn't seem to matter since nothing here uses it.

    0x100272dd2 <+10482>: movq   -0xd8(%rbp), %rbx
    0x100272dd9 <+10489>: movq   -0x198(%rbp), %r14

Here's the loop. The loop is unrolled 5 times. total+=result. 0x100274454 produces some kind of exception on integer overflow.

    0x100272de0 <+10496>: addq   %rax, %rbx
    0x100272de3 <+10499>: jb     0x100274454 ; at flatbench.swift:284
    0x100272de9 <+10505>: addq   %rax, %rbx
    0x100272dec <+10508>: jb     0x100274454
    0x100272df2 <+10514>: addq   %rax, %rbx
    0x100272df5 <+10517>: jb     0x100274454
    0x100272dfb <+10523>: addq   %rax, %rbx
    0x100272dfe <+10526>: jb     0x100274454
    0x100272e04 <+10532>: addq   %rax, %rbx
    0x100272e07 <+10535>: jb     0x100274454

The loop was unrolled 5 times, so drop 5 from the loop counter and repeat.

    0x100272e0d <+10541>: addq   $-0x5, %rcx
    0x100272e11 <+10545>: jne    0x100272de0 ; at flatbench.swift:276

Get current time.

    0x100272e13 <+10547>: callq  0x1002b7b38 ; CFAbsoluteTimeGetCurrent

So this code actually times one call to flatDecodeDirect, then 200 iterations of an unrolled do-nothing loop. The compiler has figured out somehow that flatDecodeDirect is going to do exactly the same thing each time, and taken advantage of that by calling it only once. I'm guessing this means that flatDecodeDirect is only called 1,000 times in total.

As a sanity check for this kind of thing - try making a little loop that just increments an integer the appropriate number of times, and see how long that takes. (Check the assembly language output to ensure the generated code is doing what you think - it should be a 2-instruction loop.)

On my laptop that takes 1.8ms. This isn't the absolute limit of how long it takes to do 1,000,000 of anything, but it'll do as a rough estimate. So you should be suspicious if a program suggests it's taking much less time than that to do 1,000,000 of something that's a lot more complicated, as the test did. (It reported 1,000,000 iterations in 0.53ms on my PC.)

(Of course, as with any rough estimate, this only gives you a suspicion, and isn't proof without further investigation.)

I was suspicious, I just could not put my finger on it :)

   for i in 0..<iterations {
     let result = flatuseStruct(outputData, start:i)
     assert(result == 8644311666 + Int(i))
     total2 = total2 + UInt64(result)
   }

this results in around 42ms compared to C 25ms. I guess I should update my blog post :)

Thanks for your help.