10 ms·

I wasted weeks hand optimizing assembly because I benchmarked on random data

391 points by thunderbong 1y ago

kccqzy 1y ago
Good story! I totally didn't know about the trick of changing what the JIT code produces bypassing JNI overhead. > Never have I ever seen such a highly optimized Java codebase. Not before, not since. This makes me wonder where it was. I know in the fintech world there's at least one hedge fund (not HFT, not market maker) where all their latency-sensitive trading code is written in Java, and when I asked them about GC pauses they said that their hot path produces no garbage so GC doesn't kick in.
- pengaru 1y ago
  I too knew someone in HFT ages ago that spoke of using java even in the hot path. He told me they disabled GC altogether in combination with not generating garbage in the hot path, with large enough machines to not OOM before markets closed for the day. From what I saw poking at the development trading boxes they over-provisioned both cpu ghz and ram to a ridiculous level. The machines looked nearly idle at their busiest.
  - anonymousDan 1y ago
    Yeah it always felt like they were jumping through hoops to basically write C code through Java. I expect some of this might shift to Rust..
    - kccqzy 1y ago
      Well you do get guaranteed memory safety.
      - saati 1y ago
        If they were mucking around with asm and custom jit those memory safety guarantees are gone.
  - potato3732842 1y ago
    It's a vicious cycle between provisioning more server and devs figuring out how to get more speed by using the resources for pre-computation.
  - perihelions 1y ago
    > "large enough machines to not OOM before markets closed for the day" Reminded of that missile defense system that was designed to be software-reset once a day, except the design assumptions changed (a war started) and it was ordered to be left running nonstop, as an emergency measure; after being left on for a week, failed, causing a large number of deaths. That one had some kind of integrator that accumulated floating-point roundoff over time.
    - scottlamb 1y ago
      > Reminded of that missile defense system that was designed to be software-reset once a day, except the design assumptions changed (a war started) and it was ordered to be left running nonstop, as an emergency measure I'm sure you've simplified the story, but it seems like a bit of process failure for a missile defense system to assume peacetime. There's writing software that implements the requirements, and then there's making sure the requirements are right both up front and when you really rely on them in a critical way.
    - mohaba 1y ago
      Patriot missile range gate. I remember covering that in a numerical analysis class.
    - peterfirefly 1y ago
      https://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran https://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dha...
      - scottlamb 1y ago
        I interpret that write-up to mean the daily reboot was a temporary user-suggested workaround for a bug discovered in the field, rather than something in the product specs from the beginning. And it makes more sense to me that no one realized the errors would accumulate or thought to test long operation in general than it would for them to have explicitly said it wasn't important.
        1y ago
  - renewiltord 1y ago
    Disabling GC is wildly inefficient without making sure you don't have garbage because allocation will slow down the application to human scale. The magic is more in the no-allocation code than in the disable GC side. It is very annoying in Java because any non-primitive is boxed type. Object pools etc. Problem is it's easy to start in Java, but then you hit a wall. JNI has huge overhead. Exasperating. But hard to argue, sometimes if you don't start in Java you never get the problem because you never manage to bootstrap.
  - sshine 1y ago
    I worked with low-latency trading with C# in the hot path; they had started with C++ and eventually migrated to C# and just kept tight control of allocations. Later they’d go back to using C++ for training deep neural nets.
    - pjmlp 1y ago
      To avoid going back to C++, is exactly the reason why modern .NET has native support for tensors and various SIMD flavours.
- renewiltord 1y ago
  There's quite a few. Teza definitely does, but I've spoken to many people who have done this.
- scheme271 1y ago
  Azul has a JVM that doesn't have GC pauses and has fairly good memory allocation / collection throughput.
  - throwaway2037 1y ago
    > Azul has a JVM that doesn't have GC pauses Unless GC is disabled, all GC has some pauses. You can see the chart of Azul GC pauses here: https://medium.com/@jadsarmo/why-we-chose-java-for-our-high-frequency-trading-application-600f7c04da94 https://medium.com/@jadsarmo/why-we-chose-java-for-our-high-... -> https://miro.medium.com/v2/resize:fit:1400/format:webp/1*yRG60eOIN9Yp8cjVW_vokA.png https://miro.medium.com/v2/resize:fit:1400/format:webp/1*yRG...
    - scheme271 1y ago
      That's GC duration time but the article indicates: "This is because Zing uses a unique collector called C4 (Continuously Concurrent Compacting Collector) that allows pauseless garbage collection regardless of the Java heap size (up to 8 Terabytes)." Azul's GC runs concurrrently with the app so those GC durations occur without a pause. If you think about it, there's no reason why GC requires a pause in order to work, with the right conditions, GC should be able to analyze and remove dead allocations without stopping an app.
chaosmachine 1y ago
This reminds me of Benford's law[1] "Benford's law, also known as the Newcomb–Benford law, the law of anomalous numbers, or the first-digit law, is an observation that in many real-life sets of numerical data, the leading digit is likely to be small." [1] https://en.m.wikipedia.org/wiki/Benford%27s_law https://en.m.wikipedia.org/wiki/Benford%27s_law
jasonthorsness 1y ago
Identifying a representative usage scenario to optimize towards and then implementing that scenario in a microbenchmark test driver are both massively difficult to get right, and a "failure" in this regard, as the author found, can be hard to detect before you sink a lot of time into it. Even for seemingly trivial scenarios like searching an array, the contents and length of the array make a massive difference in results and how to optimize (as shown in the last section of this write-up where I tried to benchmark search algorithms correctly https://www.jasonthorsness.com/23 https://www.jasonthorsness.com/23). I've not seen a perfect solution to this that isn't just "thinking carefully about the test setup" (profile-guided optimization/production profiles replayed for benchmarks seem like maybe it could be an alternative, but I haven't seen that used much).
- anonymoushn 1y ago
  I have asked for like the ability to apply a filter that maps real strings from real users to a very small number of character classes, so that I may run some codec on data that is equivalent to user data for the purposes of the codec. I have heard, this is not a good use of my time, and if I really care so much I should instead make various guesses about the production data distribution of user-created strings (that need to be json-escaped) and then we can deploy each of them and keep the best, if we can even tell the difference.
  - jasonthorsness 1y ago
    If the real data is sensitive, it's hard to distill test data from it that succeeds in fully removing the sensitivity but that is still useful. Depending on the domain even median string length could be sensitive.
- bgirard 1y ago
  > Identifying a representative usage scenario to optimize towards and then implementing that scenario in a microbenchmark test driver are both massively difficult to get right, and a "failure" in this regard, as the author found, can be hard to detect before you sink a lot of time into it. I can vouch for this. I've been doing web performance for nearly 15 years and finding clear representative problems is one the hardest parts of my job. Once I understood this and worked on getting better at finding representative issues, it became the single thing that I did to boost my productivity the most.
anonymoushn 1y ago
Yes, it is very important to test performance work on data distributions that are representative of the production data distribution. I hope the author has another go at using SIMD that actually makes it into use :)
zem 1y ago
> We were in the early phases of forking the JVM definitely made me go :-O - how big a company do you need to be for that to be a realistic thing to maintain in house?
- dcrazy 1y ago
  You don’t need to be big, you just need to handle lots of money.
  - zem 1y ago
    fair point, I guess this was a high frequency trading firm or similar, who could justify paying a few engineers to maintain a jvm fork
- cbzoiav 1y ago
  A fork can be many things. I've maintained in house forks of major code bases with a handful of minor code changes while we've tried to convince upstream to accept them.
- scheme271 1y ago
  Off-hand I think that there were at least 7 forks/implementations out there. Oracle/Sun, Oracle's Graal, IBM, OpenJDK, Amazon Coretto, Twitter's fork, and Azul. There's also a GNU effort but I don't think that really went very far. I think there's probably a few others that aren't publicly well known for trading firms, etc.
  - brabel 1y ago
    > there were at least 7 forks/implementations out there There are 17 listed on SDKMAN's website: https://sdkman.io/jdks https://sdkman.io/jdks > OpenJDK As far as I know, all other distributions of the JDK are forks of OpenJDK. Would love to know if there's any that isn't.
    - pjmlp 1y ago
      Commercial embedded vendors with RTOS capabilities, https://www.ptc.com/en/products/developer-tools/perc https://www.ptc.com/en/products/developer-tools/perc https://www.aicas.com/products-services/jamaicavm/ https://www.aicas.com/products-services/jamaicavm/ JikesRVM (https://www.jikesrvm.org https://www.jikesrvm.org) no longer active, but it was its own thing. Then you have Azul Zing and OpenJ9, which use parts of OpenJDK for the standard library part, but the foundations are their own thing. https://www.azul.com/products/prime/ https://www.azul.com/products/prime/ https://developer.ibm.com/components/open-j9/ https://developer.ibm.com/components/open-j9/ Then you have that mobile OS, which isn't really JVM compliant implementation, but it is close enough for many workloads and libraries to work on top of it.
scottlamb 1y ago
> For example, there was minimal use of java.lang.String because ain’t nobody got time for a second allocation of a char[] with associated indirection and GC churn. An example of why I'd prefer to avoid Java for something like that. Java has a reputation for being slow because of JIT compilation and GC, but I also think a lot of it comes down to all non-primitive types being boxed Objects (boxed = in a separate allocation). This means it works that garbage collector so much harder, there's poorer locality, it fills RAM/cache with extra Object stuff like mutexes that no one ever uses. (Apparently now 8 bytes after a lot of effort to reduce it. https://openjdk.org/jeps/450 https://openjdk.org/jeps/450)
- bsder 1y ago
  It's not like C++ users don't say the exact same thing about String, though. The problem is that String really isn't a language primitive. Different people and programs always have a different notion of what a String should do (Should it be mutable? Should it always be valid UTF-8? Which operations should be O(1), O(n) or O(n log n)? etc.)
  - scottlamb 1y ago
    > It's not like C++ users don't say the exact same thing about String, though. If they do, they're wrong, as the two languages are quite different here. In Java, String requires two allocations: your variable is implicitly a pointer to String allocation, which in turn has a pointer to a char[] allocation. In C++, the std::string itself is a value type. The actual bytes might be inline (short string optimization) or behind a single allocation accessible from the std::string. Rust's std::string::String is somewhere between: it's a value type but does not have a short string optimization (unless you count the empty string returned by String::new). > Different people and programs always have a different notion of what a String should do (Should it be mutable? Should it always be valid UTF-8? Which operations should be O(1), O(n) or O(n log n)? etc.) Sure, there can be call for writing your own String type. But what's unique about Java as compared to say C, C++, Go, Rust, even to some extent C# is that you can't have a class or struct that bundles up the parts of your data structure (in the case of a mutable string, two fields: data pointer/capacity + the used length) without boxing. There's a heavy cost to any non-primitive data type.
duxup 1y ago
I feel like this is the problem of, a lot of what I do, although not as cool as the author, and more due to human issues. I'm always looking for / wondering about valid data representing the problem so that I can measure success. A little of last and much of this week I've spent addressing a performance problem. At first I was told it was always happening in some specific situation, it very much is not. Then I was told it frequently happens ... nope, maybe 2 to 4 times a day at most. I think I've managed to track the issue down. I think so, pretty sure? On the other hand this client has a couple performance related issues ongoing and listening to them talk on a conference call... I'm not really sure they differentiate between them. It's very possible my neighbor a few seats away from me is actually addressing "the problem" and I'm chasing ghosts. But the client is too busy to provide good data. Meanwhile this issue "too important" of an issue for us to do nothing and wait, granted ... we might be doing nothing anyway.
heipei 1y ago
Counterpoint: I once wrote a paper on accelerating blockciphers (AES et al) using CUDA and while doing so I realised that most (if not all) previous academic work which had claimed incredible speedups had done so by benchmarking exclusively on zero-bytes. Since these blockciphers are implemenented using lookup tables this meant perfect cache hits on every block to be encrypted. Benchmarking on random data painted a very different, and in my opinion more realistic picture.
- atiedebee 1y ago
  Why not use real world data instead? Grab a large pdf or archive and use that as the benchmark.
  - bluGill 1y ago
    A common case is to compress data before encrypting it so random is realistic. Pdf might allow some optimization (how I don't know) that is not representative
  - jbaber 1y ago
    Or at least the canonical test vectors. All zeros is a choice.
- almostgotcaught 1y ago
  There are an enormous number of papers like this. I wrote a paper accelerating a small CNN classifier on FPGA and when I compared against the previous SOTA GPU implementation and the numbers were way off from the paper. I did a git blame on their repo and found that after the paper was published they deleted the lines that short-circuited eval if the sample was all 0 (which much of their synthetic data was ¯\_(ツ)_/¯).
- rdc12 1y ago
  Do you have a link to that paper?
- Marazan 1y ago
  Back when Genetic Algorithms were a hot topic I discovered that a large number of papers discussion optimal parameterisation of the the approach (mutation rate, cross-over, populations etc) were written using '1-Max' as the "problem" to be solved by the GA. (1-Max being attempting to make every bit of the candidate string a 1 rather than 0) This literally made the GA encoding exactly the same as the solution and also very, very obviously favoured techniques that would MAKE ALL THE BITS 1!
OhMeadhbh 1y ago
<snark>Time spent optimizing assembly language is never wasted.</snark> That's only half-snark. It was "wasted" in the sense that it wasn't as useful as the OP thought it would be. But diving deep into a technical problem? That left an indelible pattern on the OP's psyche. If they ever have to do something like that again, it will certainly be easier. And since AI is going to be doing all the simple coding tasks, humans will have to dive into the deep, hard tasks.
- xandrius 1y ago
  It could also burn someone out and take out the real reason technology exists: to help someone.
  - labadal 1y ago
    Kind of like math, huh? Some people burn out on "meaningless" impossible problems. Others get obsessed with them and make significant contributions along the way to failure.
- bluGill 1y ago
  Also there is no way for author to know that his optimizations wouldn't work without trying them. We are not even sure that his analysis of why they work is correct (though it sounds reasonable). There is also the possibility that author could use the new found information to fix his optimizations so they are better.
titzer 1y ago
I'm surprised they didn't just add a fast path of 1 and 2 byte LEBs to the hard-won assembly they generated. These fast paths are absolutely worth it. E.g. Wizard's Wasm interpreter uses a 3 instruction fastpath to decode 1-byte LEBs and then jumps out-of-line to handle the general case. It is worth 5-10% for the interpreter performance.
- phire 1y ago
  The existing implementation was already "highly optimised", so it would have had a fast path for short ints (they probably profiled on realistic data sets). Adding the fast path to the hard-won assembly is just optimising the slow path, and there is little point to optimising it. Complex optimisations are also a form of technical debt, so they are probably better off not integrating it.
- menaerus 1y ago
  The issue was that they were hand-optimizing the SIMD for a workload that doesn't even exist in their case so they ended up seeing one big nothing once they profiled the code with a new optimization - a classic trap with 95% "optimizations". It turned out that the distribution of their data is in those 1 and 2 byte LEBs, and in that case their SIMD approach doesn't give the gains as it does with 9 and 10 byte LEBs. I am wondering more about the bit-by-bit compatibility part from "This was verified in a benchmark that ran both versions on billions of random numbers, confirming both the huge speedup and the bit-for-bit compatibility of the result.". How does one test for 18.4 quintillion numbers? This isn't possible.
kazinator 1y ago
> I ended up rolling back the change, and wrote off the time spent as a proof-of-concept for developing and productionizing a custom JIT optimization. In Canada, your org can get government money for this under the SR&ED program: https://www.canada.ca/en/revenue-agency/services/scientific-research-experimental-development-tax-incentive-program.html https://www.canada.ca/en/revenue-agency/services/scientific-...
- m00x 1y ago
  You can get SR&ED for anything in Canada. Even CRUD apps get SR&ED money.
  - Joel_Mckay 1y ago
    Except the people that review your project don't necessarily keep it secret. The tax credit also won't cover Patents and Trademarks etc. which means as a startup you are vulnerable to getting scooped. YMMV =3
CactusQuipster 1y ago
[dead]
MathMonkeyMan 1y ago
Chandler Carruth told a similar story in one of his talks. He met Ken Thompson and saw beautiful C code for the first time because he had encountered a performance problem in a service. The service had to choose a policy to enforce (or something) based on the incoming request. It was taking too long to match the criteria of each potential policy against the request. Ken wrote a finite automata based pattern matcher that would simultaneously advance through all of the policies' predicates. It was perfect, and it was much faster than the existing code. Then somebody noticed that 99.9% of requests matched a particular policy, so they changed the existing code to just check that predicate first, and the code sped up a zillion times, much more than with Ken's solution.
- tasn 1y ago
  This is such a great anecdote, thanks for sharing! Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared).
  - scottlamb 1y ago
    > Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared). Exactly: profile-guided optimization is pretty awesome if you have the right infrastructure. You can get maybe 15% speedup on your program without going deep into all the code. But it has limits. IIUC, it gathers information about which code is hot, including which branches are taken, and enables certain compiler optimizations based on that. [1] But it's not going to make huge algorithm changes, it's not going to change data structure definitions [2], and it's not going to prepare good microbenchmark input for you to compare your new algorithm against the current one. Also, this article is about Java, and profile-guided optimization is something Java just has baked into its JIT already. [1] I don't know exactly which, and they likely vary by compiler version. But I think a variety of stuff to better use cache: breaking code apart into likely-"hot" vs likely-"cold" pages, deciding which loops are worth aligning, and where inlining is worthwhile. Also where branches should be optimized for likely vs unlikely vs unpredictable (conditional instructions). When it's worth autovectorizing. But it's not as good at SIMD as good as a human who puts two weeks into it, and SIMD usage is constrained by the inability to change data structures. [2] in theory, in Rust's default #[repr(Rust)] it could reorder a struct's members, but it's not going to say change from array-of-struct to struct-of-array format or hashmap to btree.
charleslmunger 1y ago
I tried implementing an optimized varint encoder that did something similar, by populating an 8 byte value and then storing it to ram, but unaligned overlapping stores caused big regressions. The approach that worked required a different technique. This one is for encoding backwards: 1. One branch for the one-byte case, always inlined, just store the byte 2. Calculate the size size of the unencoded zero prefix with a branch-free construction: (((uint32_t)clz + 7) * 9) >> 6 3. Hand roll a jump table taking advantage of arm's fixed instruction width to calculate the jump target with a shift. https://github.com/protocolbuffers/protobuf/commit/b039dfe2656dfdd358f5c9dc09b3fe447006eb63#diff-bab00d5d8c688646ecf71f3a26c4ed46b73b8cc6dd4f364df8ddc757296ddb59R162 https://github.com/protocolbuffers/protobuf/commit/b039dfe26... This results in one branch for 1 byte varints, plus one additional branch for any larger size, and the branch predictor does not have to track a varying trip count through a loop. This approach resulted in a 2.64% speedup for overall encoding (which includes a lot more than just varints) on mid sized arm cores. I think it's very difficult to beat a single comparison and branch for the 1 byte case for actual encoding forwards or backwards, unless you know there's going to be long runs of one-byte values.
grapesodaaaaa 1y ago
I can’t help but wonder what the use-case is for optimizing Java to these levels. I would expect C or asm to be a better choice at ultra high levels of optimization. I know Java can get somewhat similar performance if you put the work in, but I’d assume you want to do manual memory management at minimum.
- mcosta 1y ago
  C or asm IS a better choice at ultra high levels of optimization and crashing the process.
  - grapesodaaaaa 1y ago
    Yes, C or asm get a bad reputation. They are definitely harder. I’m just saying that this company seems to be throwing a lot of money at the problem, and at those levels you can squeeze more performance out of them and get them reasonably right. After all, many, many pieces of reliable software are written in C. If you wanted a “safer” modern language, you could pick Rust. I would just assume those would be easier picks rather than optimizing around GC pauses, which can be notoriously difficult when nanosecond matter.
    - Joel_Mckay 1y ago
      High level languages tend to hammer the allocator like a Piñata. C++ can improve code smell of C, but different languages have their own specific use-cases. The reason llvm and GC based languages is a problem in low-level real-time code is bewildering for many. Java is unique in that it often ran a dual stack for byte code, and platform specific binary objects. My advice often is to use high-level languages if you can get away with the convenience, and a low-level language with proper design patterns if you must. Many programmers I've met shouldn't write C/C++, but mostly because they can't be trusted to use memory or thread safe code. Cheers, =3
      - grapesodaaaaa 1y ago
        Agreed on a lot of that. C doesn’t inherently have to be bad (and can often be better than C++) if you are strict about adhering to standards. I like to point to OpenBSD as a successful and well-done C project. As a bonus, if you develop on OpenBSD, your program is more likely to have correct memory handling operations (OpenBSD has a lot of very aggressive memory protections. Many issues in ported applications like Firefox were found and fixed by OpenBSD users, but would happily keep running on Linux).
corysama 1y ago
Reminds me of https://ridiculousfish.com/blog/posts/old-age-and-treachery.html https://ridiculousfish.com/blog/posts/old-age-and-treachery.... Data condition can definitely affect runtime performance. All the way down to the micro architecture level. Random, sorted, reverse-sorted, uniform data sets often lead to dramatic differences in perf. Then you get into “Ooops, my dataset had a surprisingly large number of NaNs or denormalized floats!”
lqr 1y ago
In this example, random numbers provoked the worst case too often. However, in other situations random numbers are "too nice". For example, a random matrix with independent identically-distributed zero-mean entries is overwhelmingly likely to be well-conditioned, have no repeated eigenvalues, etc. Testing numerical algorithms on random data alone is a bad idea.
necovek 1y ago
I am guessing this came out of misunderstanding "profile before optimizing": you don't profile a benchmark, but a live, production system instead. Obviously, it becomes hard in such an aggressively optimized system, but if that's the case, trying and failing is an acceptable approach (I've seen 2 weeks wasted in a many a worse ways, to be honest).
- brabel 1y ago
  Optimizing for the JVM is a nightmare (or trivial depending on your point-of-view). Another anecdote: I profiled our Java-based server and concluded that most of the time was being spent on creating temporary DI containers for request handling. I spent several days trying to avoid copying the "app" scope components to the "request" scope container (we forked and heavily modified our DI container implementation) so that creating request containers was cheaper. I wrote a JMH benchmark that tried to emulate the real thing based on the real data (with something like 40% of components in the "app" scope, 60% in the "request" scope). My optimisation made the code noticably faster, I can't remember by how much exactly, but probably something like 25% faster. When I ran the "real" performance test that simulates real-world usage of the server (not just the containers) the performance was slightly worse!! Ended up throwing the code away, as the OP. I had already spent too much time on it so I couldn't dig much further into why that was. But from other experiments, I can say that the JVM, thanks to JIT compilation of bytecode, will heavily optimize the hot path anyway based on the actual usage patterns, so much that the Java code you wrote may resemble very little of what machine code is actually executing in the end. That's why I said it may also be "trivial" to optimize JVM code: just let the JIT do its job. Of course you may still obtain big gains when you optimize code that was doing stupid things, but because of JIT "magic", even your stupid code might run really fast given enough JIT passes.
  - necovek 1y ago
    Definitely, sometimes, testing in production is the only way to know something works or doesn't (or the only non-cost-prohibitive way).
necovek 1y ago
How is this encoding different from UTF-8 other than the upper boundary? There are certainly good enough encoding implementations for UTF-8, but perhaps the boundary matters.
- advisedwang 1y ago
  UTF-8 the first byte isn't just 1xxxxxxx for continuation, it's either 110xxxxx, 1110xxxx, or 11110xxx depending on how many bytes that character will take up.
  - necovek 1y ago
    Good point, I didn't pay close attention. In a sense, a shame this encoding wasn't structured like UTF-8, or even the other way around, a shame UTF-8 wasn't structured in this, more generic way.
    - advisedwang 1y ago
      ULEB128 has several deficiencies for strings: * it's not "self-synchronizing". If you jump into the middle of a ULEB128 stream and see a byte starting with 0 you can't tell whether it is a single-byte code point or the last byte of a multi-byte code-point. You have to back up to determine the meaning of the byte, which is often not viable. In fact you can't even be sure of the first 3 bytes! * Relatedly, some code-points are subsets of other code points. 0AAAAAAA appears inside of 1BBBBBBB 0AAAAAAA), so you can't search for a code point in a string without checking backwards to make sure you are comparing against a whole code point. * You can't tell the difference between a string cut at the end of a 2 byte code point and one cut part way through a 3 byte code point.
      - necovek 1y ago
        Sure, it's not perfect, and there are other issues. With UTF-8, you know exactly how many octets you need to read for the rest of the characters. But for issue #2, that seems to not be too bad since you only need to look one byte backwards. At the same time for #3, in the middle of UTF-8 bytestream, you need look backwards as well for anything but the ASCII (7-bit) codepoints too.
gorset 1y ago
In a previous project we used fixedint32/64 instead of varint values in the schema for messages where performance was critical. That left only varint used for tags. For encoding we already know the size at compile time. We also don’t have to decode them since we can match on the raw bytes (again, known at compile time). A final optimization is to make sure the message has a fixed size and then just mutate the bytes of a template directly before shipping it off. Hard to beat. In a newer project we just use SBE, but it lacks some of the ergonomics of protobuf.
fantoccio_29 1y ago
[dead]
rob_c 1y ago
Pebkac?
Havoc 1y ago
Learned that lesson with ZFS. Better to do janky testing with a cobbled together script on your own data & usage scenarios than standard tools that measure standard metrics
eulgro 1y ago
> Never have I ever seen such a highly optimized Java codebase. Not before, not since. That must be awful to work with. Why couldn't they just pick a more adequate language if they wanted performance? Or write bindings for performance critical parts?
- gf000 1y ago
  Binding can be very expensive.
mark-r 1y ago
The problem is that random numbers produced by a computer don't come close to producing naturally occurring random distributions. Your data should at the very least conform to Benford's Law (https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law).
Const-me 1y ago
LEB128 is slow and there’s no way around that. I don’t know why so many data formats are using that codec. The good variable integer encoding is the one used in MKV format: https://www.rfc-editor.org/rfc/rfc8794.html#name-variable-size-integer https://www.rfc-editor.org/rfc/rfc8794.html#name-variable-si... The compression win i.e. encoded size is equal to LEB128, however both encoding and decoding are way more efficient. The encoder is a few fast instructions for all numbers no matter large or small: bit scan reverse (or leading zero count) to find count of bits required to store the input number, division by 7 rounding up to compute count of bytes (modern compiler reliably optimize into integer multiplication and bit shifts), bitwise shift + OR to set the VINT_MARKER bit, then byte swap to store in big endian format. The decoder is equally efficient: compare first byte with 0 to detect numbers longer than 8 bytes (very rarely happens), bit scan reverse of either first or second byte to find encoded length, byte swap to load the big-endian format, then reset the most significant bit in the integer to get rid of the VINT_MARKER.
- menaerus 1y ago
  > LEB128 is slow and there’s no way around that. Actually there is - you can exploit the data parallelism through SIMD to replace the logarithmic with near-constant complexity. Classic approach indeed is very slow and unfriendly to the CPU.
  - Const-me 1y ago
    > Actually there is - you can exploit the data parallelism That doesn’t help much when you’re streaming the bytes, like many parsers or de-serializers do. You have to read bytes from the source stream one by one because each of the next byte might be the last one of the integer being decoded. You could workaround with a custom buffering adapter. Hard to do correctly, costs performance, and in some cases even impossible: when the encoded integers are coming in realtime from network, trying to read next few bytes into a RAM buffer may block. With MKV variable integers, you typically know the encoded length from just the first byte. Or in very rare cases of huge uint64 numbers, you need 2 bytes for that. Once you know the encoded length, you can read the rest of the encoded bytes with a single read function. Another thing, unless you are running on a modern AMD64 CPU which supports PDEP/PEXT instructions (parts of BMI2 ISA extension), it’s expensive to split/merge the input bits to/from these groups of 7 bits in every encoded byte. MKV variable integers don’t do that, they only need bit scan and byte swap, both instructions are available on all modern mainstream processors including ARM and are very cheap.

391 points by thunderbong 1y ago

Good story! I totally didn't know about the trick of changing what the JIT code produces bypassing JNI overhead. > Never have I ever seen such a highly optimized Java codebase. Not before, not since. This makes me wonder where it was. I know in the fintech world there's at least one hedge fund (not HFT, not market maker) where all their latency-sensitive trading code is written in Java, and when I asked them about GC pauses they said that their hot path produces no garbage so GC doesn't kick in.

pengaru 1y ago
I too knew someone in HFT ages ago that spoke of using java even in the hot path. He told me they disabled GC altogether in combination with not generating garbage in the hot path, with large enough machines to not OOM before markets closed for the day. From what I saw poking at the development trading boxes they over-provisioned both cpu ghz and ram to a ridiculous level. The machines looked nearly idle at their busiest.
- anonymousDan 1y ago
  Yeah it always felt like they were jumping through hoops to basically write C code through Java. I expect some of this might shift to Rust..
  - kccqzy 1y ago
    Well you do get guaranteed memory safety.
    - saati 1y ago
      If they were mucking around with asm and custom jit those memory safety guarantees are gone.
- potato3732842 1y ago
  It's a vicious cycle between provisioning more server and devs figuring out how to get more speed by using the resources for pre-computation.
- perihelions 1y ago
  > "large enough machines to not OOM before markets closed for the day" Reminded of that missile defense system that was designed to be software-reset once a day, except the design assumptions changed (a war started) and it was ordered to be left running nonstop, as an emergency measure; after being left on for a week, failed, causing a large number of deaths. That one had some kind of integrator that accumulated floating-point roundoff over time.
  - scottlamb 1y ago
    > Reminded of that missile defense system that was designed to be software-reset once a day, except the design assumptions changed (a war started) and it was ordered to be left running nonstop, as an emergency measure I'm sure you've simplified the story, but it seems like a bit of process failure for a missile defense system to assume peacetime. There's writing software that implements the requirements, and then there's making sure the requirements are right both up front and when you really rely on them in a critical way.
  - mohaba 1y ago
    Patriot missile range gate. I remember covering that in a numerical analysis class.
  - peterfirefly 1y ago
    https://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran https://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dha...
    - scottlamb 1y ago
      I interpret that write-up to mean the daily reboot was a temporary user-suggested workaround for a bug discovered in the field, rather than something in the product specs from the beginning. And it makes more sense to me that no one realized the errors would accumulate or thought to test long operation in general than it would for them to have explicitly said it wasn't important.
      - 1y ago
- renewiltord 1y ago
  Disabling GC is wildly inefficient without making sure you don't have garbage because allocation will slow down the application to human scale. The magic is more in the no-allocation code than in the disable GC side. It is very annoying in Java because any non-primitive is boxed type. Object pools etc. Problem is it's easy to start in Java, but then you hit a wall. JNI has huge overhead. Exasperating. But hard to argue, sometimes if you don't start in Java you never get the problem because you never manage to bootstrap.
- sshine 1y ago
  I worked with low-latency trading with C# in the hot path; they had started with C++ and eventually migrated to C# and just kept tight control of allocations. Later they’d go back to using C++ for training deep neural nets.
  - pjmlp 1y ago
    To avoid going back to C++, is exactly the reason why modern .NET has native support for tensors and various SIMD flavours.
renewiltord 1y ago
There's quite a few. Teza definitely does, but I've spoken to many people who have done this.
scheme271 1y ago
Azul has a JVM that doesn't have GC pauses and has fairly good memory allocation / collection throughput.
- throwaway2037 1y ago
  > Azul has a JVM that doesn't have GC pauses Unless GC is disabled, all GC has some pauses. You can see the chart of Azul GC pauses here: https://medium.com/@jadsarmo/why-we-chose-java-for-our-high-frequency-trading-application-600f7c04da94 https://medium.com/@jadsarmo/why-we-chose-java-for-our-high-... -> https://miro.medium.com/v2/resize:fit:1400/format:webp/1*yRG60eOIN9Yp8cjVW_vokA.png https://miro.medium.com/v2/resize:fit:1400/format:webp/1*yRG...
  - scheme271 1y ago
    That's GC duration time but the article indicates: "This is because Zing uses a unique collector called C4 (Continuously Concurrent Compacting Collector) that allows pauseless garbage collection regardless of the Java heap size (up to 8 Terabytes)." Azul's GC runs concurrrently with the app so those GC durations occur without a pause. If you think about it, there's no reason why GC requires a pause in order to work, with the right conditions, GC should be able to analyze and remove dead allocations without stopping an app.

chaosmachine 1y ago

This reminds me of Benford's law[1] "Benford's law, also known as the Newcomb–Benford law, the law of anomalous numbers, or the first-digit law, is an observation that in many real-life sets of numerical data, the leading digit is likely to be small." [1] https://en.m.wikipedia.org/wiki/Benford%27s_law https://en.m.wikipedia.org/wiki/Benford%27s_law

jasonthorsness 1y ago

Identifying a representative usage scenario to optimize towards and then implementing that scenario in a microbenchmark test driver are both massively difficult to get right, and a "failure" in this regard, as the author found, can be hard to detect before you sink a lot of time into it. Even for seemingly trivial scenarios like searching an array, the contents and length of the array make a massive difference in results and how to optimize (as shown in the last section of this write-up where I tried to benchmark search algorithms correctly https://www.jasonthorsness.com/23 https://www.jasonthorsness.com/23). I've not seen a perfect solution to this that isn't just "thinking carefully about the test setup" (profile-guided optimization/production profiles replayed for benchmarks seem like maybe it could be an alternative, but I haven't seen that used much).

anonymoushn 1y ago
I have asked for like the ability to apply a filter that maps real strings from real users to a very small number of character classes, so that I may run some codec on data that is equivalent to user data for the purposes of the codec. I have heard, this is not a good use of my time, and if I really care so much I should instead make various guesses about the production data distribution of user-created strings (that need to be json-escaped) and then we can deploy each of them and keep the best, if we can even tell the difference.
- jasonthorsness 1y ago
  If the real data is sensitive, it's hard to distill test data from it that succeeds in fully removing the sensitivity but that is still useful. Depending on the domain even median string length could be sensitive.
bgirard 1y ago
> Identifying a representative usage scenario to optimize towards and then implementing that scenario in a microbenchmark test driver are both massively difficult to get right, and a "failure" in this regard, as the author found, can be hard to detect before you sink a lot of time into it. I can vouch for this. I've been doing web performance for nearly 15 years and finding clear representative problems is one the hardest parts of my job. Once I understood this and worked on getting better at finding representative issues, it became the single thing that I did to boost my productivity the most.

anonymoushn 1y ago

Yes, it is very important to test performance work on data distributions that are representative of the production data distribution. I hope the author has another go at using SIMD that actually makes it into use :)

zem 1y ago

> We were in the early phases of forking the JVM definitely made me go :-O - how big a company do you need to be for that to be a realistic thing to maintain in house?

dcrazy 1y ago
You don’t need to be big, you just need to handle lots of money.
- zem 1y ago
  fair point, I guess this was a high frequency trading firm or similar, who could justify paying a few engineers to maintain a jvm fork
cbzoiav 1y ago
A fork can be many things. I've maintained in house forks of major code bases with a handful of minor code changes while we've tried to convince upstream to accept them.
scheme271 1y ago
Off-hand I think that there were at least 7 forks/implementations out there. Oracle/Sun, Oracle's Graal, IBM, OpenJDK, Amazon Coretto, Twitter's fork, and Azul. There's also a GNU effort but I don't think that really went very far. I think there's probably a few others that aren't publicly well known for trading firms, etc.
- brabel 1y ago
  > there were at least 7 forks/implementations out there There are 17 listed on SDKMAN's website: https://sdkman.io/jdks https://sdkman.io/jdks > OpenJDK As far as I know, all other distributions of the JDK are forks of OpenJDK. Would love to know if there's any that isn't.
  - pjmlp 1y ago
    Commercial embedded vendors with RTOS capabilities, https://www.ptc.com/en/products/developer-tools/perc https://www.ptc.com/en/products/developer-tools/perc https://www.aicas.com/products-services/jamaicavm/ https://www.aicas.com/products-services/jamaicavm/ JikesRVM (https://www.jikesrvm.org https://www.jikesrvm.org) no longer active, but it was its own thing. Then you have Azul Zing and OpenJ9, which use parts of OpenJDK for the standard library part, but the foundations are their own thing. https://www.azul.com/products/prime/ https://www.azul.com/products/prime/ https://developer.ibm.com/components/open-j9/ https://developer.ibm.com/components/open-j9/ Then you have that mobile OS, which isn't really JVM compliant implementation, but it is close enough for many workloads and libraries to work on top of it.

scottlamb 1y ago

> For example, there was minimal use of java.lang.String because ain’t nobody got time for a second allocation of a char[] with associated indirection and GC churn. An example of why I'd prefer to avoid Java for something like that. Java has a reputation for being slow because of JIT compilation and GC, but I also think a lot of it comes down to all non-primitive types being boxed Objects (boxed = in a separate allocation). This means it works that garbage collector so much harder, there's poorer locality, it fills RAM/cache with extra Object stuff like mutexes that no one ever uses. (Apparently now 8 bytes after a lot of effort to reduce it. https://openjdk.org/jeps/450 https://openjdk.org/jeps/450)

bsder 1y ago
It's not like C++ users don't say the exact same thing about String, though. The problem is that String really isn't a language primitive. Different people and programs always have a different notion of what a String should do (Should it be mutable? Should it always be valid UTF-8? Which operations should be O(1), O(n) or O(n log n)? etc.)
- scottlamb 1y ago
  > It's not like C++ users don't say the exact same thing about String, though. If they do, they're wrong, as the two languages are quite different here. In Java, String requires two allocations: your variable is implicitly a pointer to String allocation, which in turn has a pointer to a char[] allocation. In C++, the std::string itself is a value type. The actual bytes might be inline (short string optimization) or behind a single allocation accessible from the std::string. Rust's std::string::String is somewhere between: it's a value type but does not have a short string optimization (unless you count the empty string returned by String::new). > Different people and programs always have a different notion of what a String should do (Should it be mutable? Should it always be valid UTF-8? Which operations should be O(1), O(n) or O(n log n)? etc.) Sure, there can be call for writing your own String type. But what's unique about Java as compared to say C, C++, Go, Rust, even to some extent C# is that you can't have a class or struct that bundles up the parts of your data structure (in the case of a mutable string, two fields: data pointer/capacity + the used length) without boxing. There's a heavy cost to any non-primitive data type.

duxup 1y ago

I feel like this is the problem of, a lot of what I do, although not as cool as the author, and more due to human issues. I'm always looking for / wondering about valid data representing the problem so that I can measure success. A little of last and much of this week I've spent addressing a performance problem. At first I was told it was always happening in some specific situation, it very much is not. Then I was told it frequently happens ... nope, maybe 2 to 4 times a day at most. I think I've managed to track the issue down. I think so, pretty sure? On the other hand this client has a couple performance related issues ongoing and listening to them talk on a conference call... I'm not really sure they differentiate between them. It's very possible my neighbor a few seats away from me is actually addressing "the problem" and I'm chasing ghosts. But the client is too busy to provide good data. Meanwhile this issue "too important" of an issue for us to do nothing and wait, granted ... we might be doing nothing anyway.

heipei 1y ago

Counterpoint: I once wrote a paper on accelerating blockciphers (AES et al) using CUDA and while doing so I realised that most (if not all) previous academic work which had claimed incredible speedups had done so by benchmarking exclusively on zero-bytes. Since these blockciphers are implemenented using lookup tables this meant perfect cache hits on every block to be encrypted. Benchmarking on random data painted a very different, and in my opinion more realistic picture.

atiedebee 1y ago
Why not use real world data instead? Grab a large pdf or archive and use that as the benchmark.
- bluGill 1y ago
  A common case is to compress data before encrypting it so random is realistic. Pdf might allow some optimization (how I don't know) that is not representative
- jbaber 1y ago
  Or at least the canonical test vectors. All zeros is a choice.
almostgotcaught 1y ago
There are an enormous number of papers like this. I wrote a paper accelerating a small CNN classifier on FPGA and when I compared against the previous SOTA GPU implementation and the numbers were way off from the paper. I did a git blame on their repo and found that after the paper was published they deleted the lines that short-circuited eval if the sample was all 0 (which much of their synthetic data was ¯\_(ツ)_/¯).
rdc12 1y ago
Do you have a link to that paper?
Marazan 1y ago
Back when Genetic Algorithms were a hot topic I discovered that a large number of papers discussion optimal parameterisation of the the approach (mutation rate, cross-over, populations etc) were written using '1-Max' as the "problem" to be solved by the GA. (1-Max being attempting to make every bit of the candidate string a 1 rather than 0) This literally made the GA encoding exactly the same as the solution and also very, very obviously favoured techniques that would MAKE ALL THE BITS 1!

OhMeadhbh 1y ago

<snark>Time spent optimizing assembly language is never wasted.</snark> That's only half-snark. It was "wasted" in the sense that it wasn't as useful as the OP thought it would be. But diving deep into a technical problem? That left an indelible pattern on the OP's psyche. If they ever have to do something like that again, it will certainly be easier. And since AI is going to be doing all the simple coding tasks, humans will have to dive into the deep, hard tasks.

xandrius 1y ago
It could also burn someone out and take out the real reason technology exists: to help someone.
- labadal 1y ago
  Kind of like math, huh? Some people burn out on "meaningless" impossible problems. Others get obsessed with them and make significant contributions along the way to failure.
bluGill 1y ago
Also there is no way for author to know that his optimizations wouldn't work without trying them. We are not even sure that his analysis of why they work is correct (though it sounds reasonable). There is also the possibility that author could use the new found information to fix his optimizations so they are better.

titzer 1y ago

I'm surprised they didn't just add a fast path of 1 and 2 byte LEBs to the hard-won assembly they generated. These fast paths are absolutely worth it. E.g. Wizard's Wasm interpreter uses a 3 instruction fastpath to decode 1-byte LEBs and then jumps out-of-line to handle the general case. It is worth 5-10% for the interpreter performance.

phire 1y ago
The existing implementation was already "highly optimised", so it would have had a fast path for short ints (they probably profiled on realistic data sets). Adding the fast path to the hard-won assembly is just optimising the slow path, and there is little point to optimising it. Complex optimisations are also a form of technical debt, so they are probably better off not integrating it.
menaerus 1y ago
The issue was that they were hand-optimizing the SIMD for a workload that doesn't even exist in their case so they ended up seeing one big nothing once they profiled the code with a new optimization - a classic trap with 95% "optimizations". It turned out that the distribution of their data is in those 1 and 2 byte LEBs, and in that case their SIMD approach doesn't give the gains as it does with 9 and 10 byte LEBs. I am wondering more about the bit-by-bit compatibility part from "This was verified in a benchmark that ran both versions on billions of random numbers, confirming both the huge speedup and the bit-for-bit compatibility of the result.". How does one test for 18.4 quintillion numbers? This isn't possible.

kazinator 1y ago

> I ended up rolling back the change, and wrote off the time spent as a proof-of-concept for developing and productionizing a custom JIT optimization. In Canada, your org can get government money for this under the SR&ED program: https://www.canada.ca/en/revenue-agency/services/scientific-research-experimental-development-tax-incentive-program.html https://www.canada.ca/en/revenue-agency/services/scientific-...

m00x 1y ago
You can get SR&ED for anything in Canada. Even CRUD apps get SR&ED money.
- Joel_Mckay 1y ago
  Except the people that review your project don't necessarily keep it secret. The tax credit also won't cover Patents and Trademarks etc. which means as a startup you are vulnerable to getting scooped. YMMV =3

CactusQuipster 1y ago

[dead]

MathMonkeyMan 1y ago

Chandler Carruth told a similar story in one of his talks. He met Ken Thompson and saw beautiful C code for the first time because he had encountered a performance problem in a service. The service had to choose a policy to enforce (or something) based on the incoming request. It was taking too long to match the criteria of each potential policy against the request. Ken wrote a finite automata based pattern matcher that would simultaneously advance through all of the policies' predicates. It was perfect, and it was much faster than the existing code. Then somebody noticed that 99.9% of requests matched a particular policy, so they changed the existing code to just check that predicate first, and the code sped up a zillion times, much more than with Ken's solution.

tasn 1y ago
This is such a great anecdote, thanks for sharing! Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared).
- scottlamb 1y ago
  > Somehow relatedly, I still remember the first time I heard about profile-guided optimization which is essentially the same but for all of your code at once (well, same idea, not sure it's aggressive enough to reach the same result as the anecdote you shared). Exactly: profile-guided optimization is pretty awesome if you have the right infrastructure. You can get maybe 15% speedup on your program without going deep into all the code. But it has limits. IIUC, it gathers information about which code is hot, including which branches are taken, and enables certain compiler optimizations based on that. [1] But it's not going to make huge algorithm changes, it's not going to change data structure definitions [2], and it's not going to prepare good microbenchmark input for you to compare your new algorithm against the current one. Also, this article is about Java, and profile-guided optimization is something Java just has baked into its JIT already. [1] I don't know exactly which, and they likely vary by compiler version. But I think a variety of stuff to better use cache: breaking code apart into likely-"hot" vs likely-"cold" pages, deciding which loops are worth aligning, and where inlining is worthwhile. Also where branches should be optimized for likely vs unlikely vs unpredictable (conditional instructions). When it's worth autovectorizing. But it's not as good at SIMD as good as a human who puts two weeks into it, and SIMD usage is constrained by the inability to change data structures. [2] in theory, in Rust's default #[repr(Rust)] it could reorder a struct's members, but it's not going to say change from array-of-struct to struct-of-array format or hashmap to btree.

charleslmunger 1y ago

I tried implementing an optimized varint encoder that did something similar, by populating an 8 byte value and then storing it to ram, but unaligned overlapping stores caused big regressions. The approach that worked required a different technique. This one is for encoding backwards: 1. One branch for the one-byte case, always inlined, just store the byte 2. Calculate the size size of the unencoded zero prefix with a branch-free construction: (((uint32_t)clz + 7) * 9) >> 6 3. Hand roll a jump table taking advantage of arm's fixed instruction width to calculate the jump target with a shift. https://github.com/protocolbuffers/protobuf/commit/b039dfe2656dfdd358f5c9dc09b3fe447006eb63#diff-bab00d5d8c688646ecf71f3a26c4ed46b73b8cc6dd4f364df8ddc757296ddb59R162 https://github.com/protocolbuffers/protobuf/commit/b039dfe26... This results in one branch for 1 byte varints, plus one additional branch for any larger size, and the branch predictor does not have to track a varying trip count through a loop. This approach resulted in a 2.64% speedup for overall encoding (which includes a lot more than just varints) on mid sized arm cores. I think it's very difficult to beat a single comparison and branch for the 1 byte case for actual encoding forwards or backwards, unless you know there's going to be long runs of one-byte values.

grapesodaaaaa 1y ago

I can’t help but wonder what the use-case is for optimizing Java to these levels. I would expect C or asm to be a better choice at ultra high levels of optimization. I know Java can get somewhat similar performance if you put the work in, but I’d assume you want to do manual memory management at minimum.

mcosta 1y ago
C or asm IS a better choice at ultra high levels of optimization and crashing the process.
- grapesodaaaaa 1y ago
  Yes, C or asm get a bad reputation. They are definitely harder. I’m just saying that this company seems to be throwing a lot of money at the problem, and at those levels you can squeeze more performance out of them and get them reasonably right. After all, many, many pieces of reliable software are written in C. If you wanted a “safer” modern language, you could pick Rust. I would just assume those would be easier picks rather than optimizing around GC pauses, which can be notoriously difficult when nanosecond matter.
  - Joel_Mckay 1y ago
    High level languages tend to hammer the allocator like a Piñata. C++ can improve code smell of C, but different languages have their own specific use-cases. The reason llvm and GC based languages is a problem in low-level real-time code is bewildering for many. Java is unique in that it often ran a dual stack for byte code, and platform specific binary objects. My advice often is to use high-level languages if you can get away with the convenience, and a low-level language with proper design patterns if you must. Many programmers I've met shouldn't write C/C++, but mostly because they can't be trusted to use memory or thread safe code. Cheers, =3
    - grapesodaaaaa 1y ago
      Agreed on a lot of that. C doesn’t inherently have to be bad (and can often be better than C++) if you are strict about adhering to standards. I like to point to OpenBSD as a successful and well-done C project. As a bonus, if you develop on OpenBSD, your program is more likely to have correct memory handling operations (OpenBSD has a lot of very aggressive memory protections. Many issues in ported applications like Firefox were found and fixed by OpenBSD users, but would happily keep running on Linux).

corysama 1y ago

Reminds me of https://ridiculousfish.com/blog/posts/old-age-and-treachery.html https://ridiculousfish.com/blog/posts/old-age-and-treachery.... Data condition can definitely affect runtime performance. All the way down to the micro architecture level. Random, sorted, reverse-sorted, uniform data sets often lead to dramatic differences in perf. Then you get into “Ooops, my dataset had a surprisingly large number of NaNs or denormalized floats!”

lqr 1y ago

In this example, random numbers provoked the worst case too often. However, in other situations random numbers are "too nice". For example, a random matrix with independent identically-distributed zero-mean entries is overwhelmingly likely to be well-conditioned, have no repeated eigenvalues, etc. Testing numerical algorithms on random data alone is a bad idea.

necovek 1y ago

I am guessing this came out of misunderstanding "profile before optimizing": you don't profile a benchmark, but a live, production system instead. Obviously, it becomes hard in such an aggressively optimized system, but if that's the case, trying and failing is an acceptable approach (I've seen 2 weeks wasted in a many a worse ways, to be honest).

brabel 1y ago
Optimizing for the JVM is a nightmare (or trivial depending on your point-of-view). Another anecdote: I profiled our Java-based server and concluded that most of the time was being spent on creating temporary DI containers for request handling. I spent several days trying to avoid copying the "app" scope components to the "request" scope container (we forked and heavily modified our DI container implementation) so that creating request containers was cheaper. I wrote a JMH benchmark that tried to emulate the real thing based on the real data (with something like 40% of components in the "app" scope, 60% in the "request" scope). My optimisation made the code noticably faster, I can't remember by how much exactly, but probably something like 25% faster. When I ran the "real" performance test that simulates real-world usage of the server (not just the containers) the performance was slightly worse!! Ended up throwing the code away, as the OP. I had already spent too much time on it so I couldn't dig much further into why that was. But from other experiments, I can say that the JVM, thanks to JIT compilation of bytecode, will heavily optimize the hot path anyway based on the actual usage patterns, so much that the Java code you wrote may resemble very little of what machine code is actually executing in the end. That's why I said it may also be "trivial" to optimize JVM code: just let the JIT do its job. Of course you may still obtain big gains when you optimize code that was doing stupid things, but because of JIT "magic", even your stupid code might run really fast given enough JIT passes.
- necovek 1y ago
  Definitely, sometimes, testing in production is the only way to know something works or doesn't (or the only non-cost-prohibitive way).

necovek 1y ago

How is this encoding different from UTF-8 other than the upper boundary? There are certainly good enough encoding implementations for UTF-8, but perhaps the boundary matters.

advisedwang 1y ago
UTF-8 the first byte isn't just 1xxxxxxx for continuation, it's either 110xxxxx, 1110xxxx, or 11110xxx depending on how many bytes that character will take up.
- necovek 1y ago
  Good point, I didn't pay close attention. In a sense, a shame this encoding wasn't structured like UTF-8, or even the other way around, a shame UTF-8 wasn't structured in this, more generic way.
  - advisedwang 1y ago
    ULEB128 has several deficiencies for strings: * it's not "self-synchronizing". If you jump into the middle of a ULEB128 stream and see a byte starting with 0 you can't tell whether it is a single-byte code point or the last byte of a multi-byte code-point. You have to back up to determine the meaning of the byte, which is often not viable. In fact you can't even be sure of the first 3 bytes! * Relatedly, some code-points are subsets of other code points. 0AAAAAAA appears inside of 1BBBBBBB 0AAAAAAA), so you can't search for a code point in a string without checking backwards to make sure you are comparing against a whole code point. * You can't tell the difference between a string cut at the end of a 2 byte code point and one cut part way through a 3 byte code point.
    - necovek 1y ago
      Sure, it's not perfect, and there are other issues. With UTF-8, you know exactly how many octets you need to read for the rest of the characters. But for issue #2, that seems to not be too bad since you only need to look one byte backwards. At the same time for #3, in the middle of UTF-8 bytestream, you need look backwards as well for anything but the ASCII (7-bit) codepoints too.

gorset 1y ago

In a previous project we used fixedint32/64 instead of varint values in the schema for messages where performance was critical. That left only varint used for tags. For encoding we already know the size at compile time. We also don’t have to decode them since we can match on the raw bytes (again, known at compile time). A final optimization is to make sure the message has a fixed size and then just mutate the bytes of a template directly before shipping it off. Hard to beat. In a newer project we just use SBE, but it lacks some of the ergonomics of protobuf.

fantoccio_29 1y ago

[dead]

rob_c 1y ago

Pebkac?

Havoc 1y ago

Learned that lesson with ZFS. Better to do janky testing with a cobbled together script on your own data & usage scenarios than standard tools that measure standard metrics

eulgro 1y ago

> Never have I ever seen such a highly optimized Java codebase. Not before, not since. That must be awful to work with. Why couldn't they just pick a more adequate language if they wanted performance? Or write bindings for performance critical parts?

gf000 1y ago
Binding can be very expensive.

mark-r 1y ago

The problem is that random numbers produced by a computer don't come close to producing naturally occurring random distributions. Your data should at the very least conform to Benford's Law (https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law).

Const-me 1y ago

LEB128 is slow and there’s no way around that. I don’t know why so many data formats are using that codec. The good variable integer encoding is the one used in MKV format: https://www.rfc-editor.org/rfc/rfc8794.html#name-variable-size-integer https://www.rfc-editor.org/rfc/rfc8794.html#name-variable-si... The compression win i.e. encoded size is equal to LEB128, however both encoding and decoding are way more efficient. The encoder is a few fast instructions for all numbers no matter large or small: bit scan reverse (or leading zero count) to find count of bits required to store the input number, division by 7 rounding up to compute count of bytes (modern compiler reliably optimize into integer multiplication and bit shifts), bitwise shift + OR to set the VINT_MARKER bit, then byte swap to store in big endian format. The decoder is equally efficient: compare first byte with 0 to detect numbers longer than 8 bytes (very rarely happens), bit scan reverse of either first or second byte to find encoded length, byte swap to load the big-endian format, then reset the most significant bit in the integer to get rid of the VINT_MARKER.

menaerus 1y ago
> LEB128 is slow and there’s no way around that. Actually there is - you can exploit the data parallelism through SIMD to replace the logarithmic with near-constant complexity. Classic approach indeed is very slow and unfriendly to the CPU.
- Const-me 1y ago
  > Actually there is - you can exploit the data parallelism That doesn’t help much when you’re streaming the bytes, like many parsers or de-serializers do. You have to read bytes from the source stream one by one because each of the next byte might be the last one of the integer being decoded. You could workaround with a custom buffering adapter. Hard to do correctly, costs performance, and in some cases even impossible: when the encoded integers are coming in realtime from network, trying to read next few bytes into a RAM buffer may block. With MKV variable integers, you typically know the encoded length from just the first byte. Or in very rare cases of huge uint64 numbers, you need 2 bytes for that. Once you know the encoded length, you can read the rest of the encoded bytes with a single read function. Another thing, unless you are running on a modern AMD64 CPU which supports PDEP/PEXT instructions (parts of BMI2 ISA extension), it’s expensive to split/merge the input bits to/from these groups of 7 bits in every encoded byte. MKV variable integers don’t do that, they only need bit scan and byte swap, both instructions are available on all modern mainstream processors including ARM and are very cheap.