10 ms·

How to write slow Rust code

107 points by Reventlov 5y ago

sharikone 5y ago
Conclusion is sound. Java/Rust/C/C++... are all fast enough that the bottleneck does not reside with the choice of the language. I wonder about how Common Lisp can be this fast however. I would like comparisons with languages like Python, JS and Lua.
- Hemospectrum 5y ago
  Common Lisp has always had pretty good support for compiling to fast machine code. Most people underestimate it, for at least two reasons. One is that it doesn’t have good standing in popular benchmarks relative to C, even with speedy implementations like SBCL, and the common takeaway from such benchmarks is that a language is either as fast as C or infinitely slow. The second reason is that the process of building standalone executables is less accessible than in other languages; even to people familiar with Lisp’s strengths, it’s kind of arcane, giving off the impression that deploying CL code in production is an unsolved problem. Also, Lisp is an old language family, and the quirks of Common Lisp in particular are weird and unfamiliar when coming from any modern language, even Clojure.
- likeabbas 5y ago
  There’s a distinct difference between Java and Rust/C++ which is that Java has a stop-the-world-GC and rust/c++ don’t. And in large scale systems, Java’s GC is usually the limiting factor.
  - nlitened 5y ago
    If I understand correctly, modern Java has multiple GC engines available (that can be chosen with a command-line switch), some of which are either fully concurrent or with sub-millisecond stop times.
  - pjmlp 5y ago
    Yeah, like 1ms when handling heaps of 3TB sizes, when most people are still complaining about 16 GB on laptops, I can live with that.
    - Diggsey 5y ago
      Firstly, 1ms for a 3TB heap size is very unrealistic even for modern JVMs. Secondly, the figures that are often quoted for how long the program must be stopped are for the "happy path" where enough memory can be freed that the program can continue without issue. In practice, what often happens with large heap sizes is that the GC starts lagging behind because there's not enough memory head-room. In these cases, the GC stops the world for much longer, because the program hangs on a memory allocation that cannot be satisfied until the GC completes. This primarily affects programs that have high rates of allocation. You can avoid this in Java with effort, but you end up with very non-idiomatic code.
      - pjmlp 5y ago
        Enjoy, https://malloc.se/blog/zgc-jdk16 https://malloc.se/blog/zgc-jdk16 I guess Oracle, IBM, Azul, PTC, Microsoft can provide the necessary data about their pauseless GC implementantions to any relevant customer.
      - native_samples 5y ago
        Modern JVMs have a GC that has O(1) pause times, often of less than 1msec regardless of heap size. In ZGC and Shenandoah, GC is fully concurrent and pauses are basically imperceptible. Even walking the stacks to locate pointers into the heap is done whilst the application is still running.
  - nobleach 5y ago
    Newer versions of Java have more interesting GC implementations that reduce that "stop the world, swab the decks" performance. The fine engineers working on the JVM keep finding ways to incrementally garbage collect. It's getting to a point where it's imperceptible in some applications. Granted, if you're writing high-speed/high-frequency trading apps for Wall Street, Java still isn't there. Rust could be the logical next step in that arena. (Although, most C++ devs I know in that space don't hate C++)
    - lordnacho 5y ago
      > if you're writing high-speed/high-frequency trading apps for Wall Street, Java still isn't there A fair few trading system job ads seem to be for Java. I also wrote code that faced a Java server at various banks. Seems to be fast enough for certain market related applications.
      - tuxman 5y ago
        From my understanding of previous talks on this, a fair amount of HFT's and trading firms use Java. The trick is that the trading day is a well-defined window with clear starts and stops. So if you load up your server with huge amounts of memory, you can get away with never calling GC during the trading day. The GC can be paused until after hours or just kill the program and start it up before market open the next day.
        nobleach 5y ago
        One solution I had been dying to implement is the Erlang style of letting a Kubernetes POD OOM, and just respawning it. If the app performs well right up until it runs out of memory, I see no reason to have a GC turned on at all. (obviously there ARE reasons, I just wanted to try this approach)
      - magila 5y ago
        The use of Java in trading systems is widely misunderstood. Java is typically used to implement the high level business logic where microsecond latency is not required. The output of the Java service is feed to another system which handles the actual trade execution. That part is typically done with C++, or FPGAs driven by C++.
- bjoli 5y ago
  SBCL is fast. People seem to lump together dynamically typed languages, but the reality is that python and ruby forgot all the things learned during the 80s and early 90s. My experience is that small programs like this are usually at least an order of magnitude faster in SBCL compared to python. At least if the python code spends some time in actual python instead of offloading to C.
  - omginternets 5y ago
    >ruby forgot all the things learned during the 80s and early 90s Out of curiosity, what things are you referring to?
    - bjoli 5y ago
      From the top of my head before I get off the bus: Things like proper static modules so that you know what is being called so you can elide lookups at call-time. That is a pretty big omission, TBH. For a long time (still?) python had a horribly inefficient value representation in memory. Now, integer tagging is probably no fun to add as an afterthought, but it shouldn't have been an afterthought. Exception handling is sloooow. And iterators use exceptions to signal that younhave exhausted the collection. Because iterating over a complete collection is exceptional. I understand the need to keep cpython simple, but some of these things ARE simple and have been well understood since a decade before python 1.0.
      - orf 5y ago
        Static modules with elided lookups is completely nonsensical in Python. StopIteration is special-cased and has negligible overhead. See here (https://www.python.org/dev/peps/pep-0234/ https://www.python.org/dev/peps/pep-0234/) for why exceptions are used.
        bjoli 5y ago
        On the contrary. Static modules would mean static classes with no possibility of changing a class. That would be another pretty nice optimization you could do, making class lookups a lot faster. I am not alone in thinking this would be a good idea. The Instagram folks wrote about it, iirc. That rationale for using an exception is only valid because CPython procedure calls are expensive. A proper optimizing compiler will have a hard time rewriting that implicit try/catch into a goto. I think Dart nailed iterators in this regard: no special values, and a protocol that is transparent to the compiler, which has the benefit of requiring no special cases at all. In the current state of cpython, of course, that falls into the "2 expensive procedure calls that can't be inlined because everything can be mutated at any time" type of a problem.
- pjmlp 5y ago
  Lisp was used to write full OSes, naturally it is fast. Python, JS and Lua are not in the same league of AOT and JIT compiler technology available to Lisp, even with all the money spent on stuff like V8, JS JIT cannot compensate for the fact that they lack the ability to provide the required semantics to AOT code with good enough performance to write a Xerox PARC graphical workstation (see Interlisp-D). It is no wonder that Julia, a Lisp like language with Algol syntax, is the only modern dynamic language on the HPC club. https://www.hpcwire.com/off-the-wire/julia-joins-petaflop-club/ https://www.hpcwire.com/off-the-wire/julia-joins-petaflop-cl...
  - Banana699 5y ago
    I think Julia being an HPC lang despite dynamicity has nothing to do with being close to lisp in some regards. I didn't use the language but the overwhelming community consensus I get is that performance is out of the window once you truly embrace dynamic (type-unstable in julia parlance) code. Julia performance depends heavily on the compiler being able to infer a single type for variables in the hot loop so that it can specialize the used functions to it then get out of the way. Julia is not a Fortran-speed python, it's a language that can be _either_ Fortran _or_ python, depending on how you write it. Lisp influences on julia are more for semantic power than performance.
    - pjmlp 5y ago
      Depends on how one sees it, https://www.researchgate.net/publication/267008293_Fast_floating-point_processing_in_Common_Lisp https://www.researchgate.net/publication/267008293_Fast_floa... The point being what dynamic homoiconic languages are able to achieve when the community actually embraces the push for performance instead of hand waving and rewriting everything in C. If the JavaScript community had the same attitude as Python one, surely we would still be doing HTML 4 without pesky SPAs.
- divs1210 5y ago
  SBCL and Chez Scheme are probably the most advanced dynamic language environments around. Unfortunately, CL has started to show its age (case insensitive, different namespaces for variables and functions, weirdly named stuff, etc.) and Chez Scheme doesn't have a lot of libraries. In my experience, Chez Scheme is very small, blazing fast, and VERY high level. It is a great platform to use as a target language for compilers / interpreters. Racket has chosen to go this route, for example.
  - phoe-krk 5y ago
    Can't say that different namespaces are a sign of Lisp showing its age. At least in my mental model, it is convenient to know that a single symbol can name several different things in different namespaces at the same time - e.g. a variable, a function, a type, and a few more that are possibly defined by the user. Enforcing the "strictly one meaning per symbol" paradigm seems pretty self-defeating to me, since even in a Lisp-1 users can - and eventually will - create their own namespaces, implementing a Lisp-N themselves.
  - pjmlp 5y ago
    Kind of, SBCL doesn't have the tooling of Allegro or LispWorks.
- tialaramex 5y ago
  > the bottleneck does not reside with the choice of the language. I think that's too bold a claim. Your code might be too slow in any of these languages because you made poor algorithmic or data structure choices but once you have made the best possible algorithmic and data structure choices you may reach a point where you can't express the program with the choices you need and get the desired performance in some languages. At that point, in the immediate present, you have to choose the tool that actually gets the job done. It doesn't matter if C++ could totally hit your numbers "once that LLVM optimiser bug gets fixed" or if Java could do it "when they port the new JIT to our platform", you need the thing that works now. Over the medium term, language evolution makes an impact here. Once upon a time C++ didn't have move semantics. Obviously in some cases your compiler can move as an optimisation, but in other cases if you can't ask for one explicitly you're often out of luck. However C++ has a specific performance goal ("Leave no room for a lower-level language") that guides them to find a way to get great performance, and they changed the C++ language to fix this. If your ideal solution is slow in C++ then the C++ committee ostensibly wants to fix that. Just maybe not this year. In contrast for Java performance is not a primary goal and sometimes Java is OK with worse performance. In this particular essay it happens for RAM consumption. This problem shouldn't run out of RAM on your mid-1990s server at the scale demonstrated, but the Java solution would either run out of RAM or spin up the GC mid-solution (and thus ruin speed). No argument that "I'll rewrite it in Rust/C++" is just as much the wrong first instinct as "I'll hand roll the assembler". But if you're under-performing with the right algorithm you need to either spend money on more (faster/ bigger) hardware or on rewriting in the language that might buy you that last drop of performance.
- ostenning 5y ago
  Not for embedded environments
- gameswithgo 5y ago
  fast enough for this workload. If you were trying to maintain 144fps with some kind of 3d interface with no frame drops, any garbage collector will be a challenge.
phoe-krk 5y ago
It seems true to me that working with the Rust borrow checker is eventually fruitful, but this post shows a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. There is a part over there that compares: (cons word words) to: let mut partial_solution = words.clone(); partial_solution.push(word); In this particular case this isn't Rust being slow, this is an attempt to compare a O(1) cons operation to a O(n) process of copying a list. Doing this N times results in accidentally quadratic complexity for Rust - no doubt it's slow. I cannot say much more about Rust syntax since I am even more of a Rust newbie than the author - perhaps someone can have some further comments on the quality of the resultant Rust code. Still, the Lisp version can be pushed even further with regards to performance - it still lacks explicit type declarations and I am unsure if the author asked the Lisp compiler to optimize for speed and resolved any notes that the compiler might have produced.
- Cu3PO42 5y ago
  > It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. I fully agree. In the past year I have worked in Rust a lot and while quarrels with the borrow checker have definitely gotten more and more rare, they still happen occasionally. It's not that the borrow checker presents a reason which I think is incorrect or invalid, it's rather that it's sometimes difficult or just tedious to encode the proof that what you're doing is actually fine. That said, there have been situations in which I was absolutely confident my code would have been fine if it weren't for the meddling borrow checker, but it actually wasn't and it helped me catch bugs. Fortunately there is a bit of an escape hatch: if you want to, you can just start reference counting and get close to the experience you'd have with a proper GC. For example, there's nothing preventing you from implementing a reference counted linked list and writing LinkedList::Cons(word, words)
  - nybble41 5y ago
    In this case the linked list is just tracking "breadcrumbs" which mirror the path back up the call chain, so you don't even need reference counting; a simple borrowed reference will do. I put together a version in Rust based on stack-allocated linked lists[0], and the results were promising: on 10 million inputs the Rust version completes in about 40 seconds on my machine, while the Java port (Main2.java in the code; "Java1" from the article IIUC) takes 82 seconds. This Rust version doesn't allocate anything from the heap, apart from loading the dictionary at startup; all the bookkeeping, including the cons cells, is kept on the stack. [0] https://github.com/nybble41/prechelt-phone-number-encoding https://github.com/nybble41/prechelt-phone-number-encoding
Zababa 5y ago
If you look at the memory data https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=2144982248 https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFL..., Rust seems like the only one that uses constant memory, and it uses way less than the others. The other thing that I get from this article is that performance is really complex, and never just a function of the language you chose. I'm glad to read articles like that as a junior, I think this will give me a good mental model for performance.
- mamcx 5y ago
  >and never just a function of the language you chose. I understand your point, but is important to know how NUANCED is this. Performance is MOSTLY driven by the inherent design choices of each language(+ your own!). If you are on Gc, that choice is an impact for everything. Rust have Vectors as base, and lisp have GC-backed linked list. That is another deeeeep choice. But IF you know (or hit the luck!) which are these designs, and understand that not matter which language everyone wanna gotta fast and most common operations (the ones for what THAT lang was designed for!) are fast enough... then all is ok, in average. Is when you go against that design that you see how the illusion crack a little. Then, is all about how much you can workaround about it to recover most of the performance
  - pjmlp 5y ago
    Or when one fails to understand what is actually available to them on the toolbox and only look for what is visible at top level. For example, yes Lisps have a GC backed linked list, but in the case of Common Lisp, they also have arrays, stack allocation and deterministic resource management macros.
  - Zababa 5y ago
    That is very true, for example Java, even while being as fast as Rust and Lisp, takes way more memory than both of them. My point was more for myself (and maybe other people that haven't heard a lot about performance), as I had very strict ideas about it, but thanks to articles like that I can understand how it's more nuanced. Software engineering and computer science are both really vast and deep fields, but a lot of information is here online, shared freely by awesome people. That means that for a lot of things, being aware of something is enough to make good decisions. These types of articles allows me to be more aware of the nuances of performance (and how complex it is as a topic). For example, if I'm just trying to optimize the speed of my algorithm, and only know Java, Java might be enough. But if I'm trying to optimize my cloud spendings, considering the memory consumption of Java, it might not be the best choice. Comments like yours are also a great way to learn more. I know that linked-lists are really good in Lisp (and OCaml too!), but with other languages there's not often the best choice.
brundolf 5y ago
Implementing a Lisp cons algorithm as-is using a Vec is so far from being apples-to-apples that it makes me question the results of the entire article, despite the fact that things were eventually "optimized" to not do this. Gathering a list by calling cons over and over is only remotely advisable when you're working with a linked-list (which you are, in Lisp). Blindly replacing it with a Vec demonstrates either a total ignorance of CS fundamentals, or a willingness for the benchmarks to come out a certain way. A real "apples-to-apples" comparison would at least have Rust using an actual linked-list for this algorithm. A mutable Vec is more idiomatic and probably more efficient, but cloning an immutable Vec at every step turns O(N) into O(N^2). Note that this isn't Rust apologism: the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. Most languages' go-to structures for holding a sequence have roughly the performance characteristics of a vector. I guess the article at least fulfills its title: "How to write slow Rust code"
- phoe-krk 5y ago
  > the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. ...or, to be fully honest, a Common Lisp VECTOR that is then CONCATENATE'd with a new element at its beginning. As I said in another comment, this isn't the problem of using a given language - it's the problem of using a wrong data structure for the job.
  - brundolf 5y ago
    Exactly. And the fact that it's framed as "well I just wanted a straight comparison, I didn't want to wade too far into idioms and Rust-isms in the first pass" feels disingenuous.
- lalaithion 5y ago
  The more general view to take from this is that when you program a lot in one language, you get so used to certain performance patterns that you simply write your code in a way that takes advantage of them first try[1]. Peter Norvig's Lisp solution is an optimized solution for Lisp in a lot of little ways. Directly translating an optimized-for-Lisp program into any other language is silly, because you miss out on the optimizations available in that language to an experienced programmer and you lose out doing pointless things which were essential in Lisp.
xondono 5y ago
It might be just the write up, but the article reads like he was playing with the benchmarks until he got a result where Java was faster. I don’t think anything malicious has happened, just pointing out that benchmarking is hard, and changing parameters just to see what happens is not benchmarking. I haven’t gone deep enough into the code and the problem, but it looks like this: What if we swap the Rust HashMap implementation, as they say the standard one I was using applies a cryptographically-safe hash that the JVM doesn’t Is quite a distinction, especially for the latter cases with lengthier phone numbers.
lkey 5y ago
I don't recommend drawing too much of a conclusion from these tests, about anything other than printing in <your language>. Once the algorithm is somewhat optimized, the benchmark is completely dominated by printing to stdout, not the algorithm in question. Pulling from the near the conclusion here, bugaevc finds: "And the measured time reflects how long it take to actually compute the solutions (≈1.6s), not how much time it takes to output/buffer them (≈59s)." source: https://github.com/renatoathaydes/prechelt-phone-number-encoding/pull/1 https://github.com/renatoathaydes/prechelt-phone-number-enco...
kennywinker 5y ago
I got a lot out of this article, thanks! One of my problems with learning rust has been the “draw the f**ing owl” problem. There are lots of tutorials on getting started, and while advanced code is easy to find i have not found a lot of intermediate or advanced code with good explanatory annotations. Great seeing someone take beginner code and rustify it!
- mst 5y ago
  Right, I really enjoyed it on that basis too. I'm quite amazed how many of the responses are criticising his original code when the whole point of the article is that his original code was n00btastic and he's very grateful to've been helped to improve it and wanted to share.
  - igouy 5y ago
    > … his original code was n00btastic… Sorry, but this is at-least the second blog post, in the last week, and previously — "I've discussed the Rust and Julia versions with experts in those languages (—— I know Rust well enough ——, but very little Julia) and no obvious mistakes were found." https://www.reddit.com/r/lisp/comments/osqgqe/common_lisp_still_beats_java_rust_julia_dart_in/h6qd67d/ https://www.reddit.com/r/lisp/comments/osqgqe/common_lisp_st... Before that, on finding the output from his Java program was different than the output from Peter Norvig's Lisp program — "It looks like Norvig's Lisp solution must have a bug: it can't find all valid solutions!" https://github.com/renatoathaydes/prechelt-phone-number-encoding/tree/rust-optimised https://github.com/renatoathaydes/prechelt-phone-number-enco...
mastrsushi 5y ago
By writing anything :^)

107 points by Reventlov 5y ago

Conclusion is sound. Java/Rust/C/C++... are all fast enough that the bottleneck does not reside with the choice of the language. I wonder about how Common Lisp can be this fast however. I would like comparisons with languages like Python, JS and Lua.

Hemospectrum 5y ago
Common Lisp has always had pretty good support for compiling to fast machine code. Most people underestimate it, for at least two reasons. One is that it doesn’t have good standing in popular benchmarks relative to C, even with speedy implementations like SBCL, and the common takeaway from such benchmarks is that a language is either as fast as C or infinitely slow. The second reason is that the process of building standalone executables is less accessible than in other languages; even to people familiar with Lisp’s strengths, it’s kind of arcane, giving off the impression that deploying CL code in production is an unsolved problem. Also, Lisp is an old language family, and the quirks of Common Lisp in particular are weird and unfamiliar when coming from any modern language, even Clojure.
likeabbas 5y ago
There’s a distinct difference between Java and Rust/C++ which is that Java has a stop-the-world-GC and rust/c++ don’t. And in large scale systems, Java’s GC is usually the limiting factor.
- nlitened 5y ago
  If I understand correctly, modern Java has multiple GC engines available (that can be chosen with a command-line switch), some of which are either fully concurrent or with sub-millisecond stop times.
- pjmlp 5y ago
  Yeah, like 1ms when handling heaps of 3TB sizes, when most people are still complaining about 16 GB on laptops, I can live with that.
  - Diggsey 5y ago
    Firstly, 1ms for a 3TB heap size is very unrealistic even for modern JVMs. Secondly, the figures that are often quoted for how long the program must be stopped are for the "happy path" where enough memory can be freed that the program can continue without issue. In practice, what often happens with large heap sizes is that the GC starts lagging behind because there's not enough memory head-room. In these cases, the GC stops the world for much longer, because the program hangs on a memory allocation that cannot be satisfied until the GC completes. This primarily affects programs that have high rates of allocation. You can avoid this in Java with effort, but you end up with very non-idiomatic code.
    - pjmlp 5y ago
      Enjoy, https://malloc.se/blog/zgc-jdk16 https://malloc.se/blog/zgc-jdk16 I guess Oracle, IBM, Azul, PTC, Microsoft can provide the necessary data about their pauseless GC implementantions to any relevant customer.
    - native_samples 5y ago
      Modern JVMs have a GC that has O(1) pause times, often of less than 1msec regardless of heap size. In ZGC and Shenandoah, GC is fully concurrent and pauses are basically imperceptible. Even walking the stacks to locate pointers into the heap is done whilst the application is still running.
- nobleach 5y ago
  Newer versions of Java have more interesting GC implementations that reduce that "stop the world, swab the decks" performance. The fine engineers working on the JVM keep finding ways to incrementally garbage collect. It's getting to a point where it's imperceptible in some applications. Granted, if you're writing high-speed/high-frequency trading apps for Wall Street, Java still isn't there. Rust could be the logical next step in that arena. (Although, most C++ devs I know in that space don't hate C++)
  - lordnacho 5y ago
    > if you're writing high-speed/high-frequency trading apps for Wall Street, Java still isn't there A fair few trading system job ads seem to be for Java. I also wrote code that faced a Java server at various banks. Seems to be fast enough for certain market related applications.
    - tuxman 5y ago
      From my understanding of previous talks on this, a fair amount of HFT's and trading firms use Java. The trick is that the trading day is a well-defined window with clear starts and stops. So if you load up your server with huge amounts of memory, you can get away with never calling GC during the trading day. The GC can be paused until after hours or just kill the program and start it up before market open the next day.
      - nobleach 5y ago
        One solution I had been dying to implement is the Erlang style of letting a Kubernetes POD OOM, and just respawning it. If the app performs well right up until it runs out of memory, I see no reason to have a GC turned on at all. (obviously there ARE reasons, I just wanted to try this approach)
    - magila 5y ago
      The use of Java in trading systems is widely misunderstood. Java is typically used to implement the high level business logic where microsecond latency is not required. The output of the Java service is feed to another system which handles the actual trade execution. That part is typically done with C++, or FPGAs driven by C++.
bjoli 5y ago
SBCL is fast. People seem to lump together dynamically typed languages, but the reality is that python and ruby forgot all the things learned during the 80s and early 90s. My experience is that small programs like this are usually at least an order of magnitude faster in SBCL compared to python. At least if the python code spends some time in actual python instead of offloading to C.
- omginternets 5y ago
  >ruby forgot all the things learned during the 80s and early 90s Out of curiosity, what things are you referring to?
  - bjoli 5y ago
    From the top of my head before I get off the bus: Things like proper static modules so that you know what is being called so you can elide lookups at call-time. That is a pretty big omission, TBH. For a long time (still?) python had a horribly inefficient value representation in memory. Now, integer tagging is probably no fun to add as an afterthought, but it shouldn't have been an afterthought. Exception handling is sloooow. And iterators use exceptions to signal that younhave exhausted the collection. Because iterating over a complete collection is exceptional. I understand the need to keep cpython simple, but some of these things ARE simple and have been well understood since a decade before python 1.0.
    - orf 5y ago
      Static modules with elided lookups is completely nonsensical in Python. StopIteration is special-cased and has negligible overhead. See here (https://www.python.org/dev/peps/pep-0234/ https://www.python.org/dev/peps/pep-0234/) for why exceptions are used.
      - bjoli 5y ago
        On the contrary. Static modules would mean static classes with no possibility of changing a class. That would be another pretty nice optimization you could do, making class lookups a lot faster. I am not alone in thinking this would be a good idea. The Instagram folks wrote about it, iirc. That rationale for using an exception is only valid because CPython procedure calls are expensive. A proper optimizing compiler will have a hard time rewriting that implicit try/catch into a goto. I think Dart nailed iterators in this regard: no special values, and a protocol that is transparent to the compiler, which has the benefit of requiring no special cases at all. In the current state of cpython, of course, that falls into the "2 expensive procedure calls that can't be inlined because everything can be mutated at any time" type of a problem.
pjmlp 5y ago
Lisp was used to write full OSes, naturally it is fast. Python, JS and Lua are not in the same league of AOT and JIT compiler technology available to Lisp, even with all the money spent on stuff like V8, JS JIT cannot compensate for the fact that they lack the ability to provide the required semantics to AOT code with good enough performance to write a Xerox PARC graphical workstation (see Interlisp-D). It is no wonder that Julia, a Lisp like language with Algol syntax, is the only modern dynamic language on the HPC club. https://www.hpcwire.com/off-the-wire/julia-joins-petaflop-club/ https://www.hpcwire.com/off-the-wire/julia-joins-petaflop-cl...
- Banana699 5y ago
  I think Julia being an HPC lang despite dynamicity has nothing to do with being close to lisp in some regards. I didn't use the language but the overwhelming community consensus I get is that performance is out of the window once you truly embrace dynamic (type-unstable in julia parlance) code. Julia performance depends heavily on the compiler being able to infer a single type for variables in the hot loop so that it can specialize the used functions to it then get out of the way. Julia is not a Fortran-speed python, it's a language that can be _either_ Fortran _or_ python, depending on how you write it. Lisp influences on julia are more for semantic power than performance.
  - pjmlp 5y ago
    Depends on how one sees it, https://www.researchgate.net/publication/267008293_Fast_floating-point_processing_in_Common_Lisp https://www.researchgate.net/publication/267008293_Fast_floa... The point being what dynamic homoiconic languages are able to achieve when the community actually embraces the push for performance instead of hand waving and rewriting everything in C. If the JavaScript community had the same attitude as Python one, surely we would still be doing HTML 4 without pesky SPAs.
divs1210 5y ago
SBCL and Chez Scheme are probably the most advanced dynamic language environments around. Unfortunately, CL has started to show its age (case insensitive, different namespaces for variables and functions, weirdly named stuff, etc.) and Chez Scheme doesn't have a lot of libraries. In my experience, Chez Scheme is very small, blazing fast, and VERY high level. It is a great platform to use as a target language for compilers / interpreters. Racket has chosen to go this route, for example.
- phoe-krk 5y ago
  Can't say that different namespaces are a sign of Lisp showing its age. At least in my mental model, it is convenient to know that a single symbol can name several different things in different namespaces at the same time - e.g. a variable, a function, a type, and a few more that are possibly defined by the user. Enforcing the "strictly one meaning per symbol" paradigm seems pretty self-defeating to me, since even in a Lisp-1 users can - and eventually will - create their own namespaces, implementing a Lisp-N themselves.
- pjmlp 5y ago
  Kind of, SBCL doesn't have the tooling of Allegro or LispWorks.
tialaramex 5y ago
> the bottleneck does not reside with the choice of the language. I think that's too bold a claim. Your code might be too slow in any of these languages because you made poor algorithmic or data structure choices but once you have made the best possible algorithmic and data structure choices you may reach a point where you can't express the program with the choices you need and get the desired performance in some languages. At that point, in the immediate present, you have to choose the tool that actually gets the job done. It doesn't matter if C++ could totally hit your numbers "once that LLVM optimiser bug gets fixed" or if Java could do it "when they port the new JIT to our platform", you need the thing that works now. Over the medium term, language evolution makes an impact here. Once upon a time C++ didn't have move semantics. Obviously in some cases your compiler can move as an optimisation, but in other cases if you can't ask for one explicitly you're often out of luck. However C++ has a specific performance goal ("Leave no room for a lower-level language") that guides them to find a way to get great performance, and they changed the C++ language to fix this. If your ideal solution is slow in C++ then the C++ committee ostensibly wants to fix that. Just maybe not this year. In contrast for Java performance is not a primary goal and sometimes Java is OK with worse performance. In this particular essay it happens for RAM consumption. This problem shouldn't run out of RAM on your mid-1990s server at the scale demonstrated, but the Java solution would either run out of RAM or spin up the GC mid-solution (and thus ruin speed). No argument that "I'll rewrite it in Rust/C++" is just as much the wrong first instinct as "I'll hand roll the assembler". But if you're under-performing with the right algorithm you need to either spend money on more (faster/ bigger) hardware or on rewriting in the language that might buy you that last drop of performance.
ostenning 5y ago
Not for embedded environments
gameswithgo 5y ago
fast enough for this workload. If you were trying to maintain 144fps with some kind of 3d interface with no frame drops, any garbage collector will be a challenge.

phoe-krk 5y ago

It seems true to me that working with the Rust borrow checker is eventually fruitful, but this post shows a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. There is a part over there that compares: (cons word words) to: let mut partial_solution = words.clone(); partial_solution.push(word); In this particular case this isn't Rust being slow, this is an attempt to compare a O(1) cons operation to a O(n) process of copying a list. Doing this N times results in accidentally quadratic complexity for Rust - no doubt it's slow. I cannot say much more about Rust syntax since I am even more of a Rust newbie than the author - perhaps someone can have some further comments on the quality of the resultant Rust code. Still, the Lisp version can be pushed even further with regards to performance - it still lacks explicit type declarations and I am unsure if the author asked the Lisp compiler to optimize for speed and resolved any notes that the compiler might have produced.

Cu3PO42 5y ago
> It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. I fully agree. In the past year I have worked in Rust a lot and while quarrels with the borrow checker have definitely gotten more and more rare, they still happen occasionally. It's not that the borrow checker presents a reason which I think is incorrect or invalid, it's rather that it's sometimes difficult or just tedious to encode the proof that what you're doing is actually fine. That said, there have been situations in which I was absolutely confident my code would have been fine if it weren't for the meddling borrow checker, but it actually wasn't and it helped me catch bugs. Fortunately there is a bit of an escape hatch: if you want to, you can just start reference counting and get close to the experience you'd have with a proper GC. For example, there's nothing preventing you from implementing a reference counted linked list and writing LinkedList::Cons(word, words)
- nybble41 5y ago
  In this case the linked list is just tracking "breadcrumbs" which mirror the path back up the call chain, so you don't even need reference counting; a simple borrowed reference will do. I put together a version in Rust based on stack-allocated linked lists[0], and the results were promising: on 10 million inputs the Rust version completes in about 40 seconds on my machine, while the Java port (Main2.java in the code; "Java1" from the article IIUC) takes 82 seconds. This Rust version doesn't allocate anything from the heap, apart from loading the dictionary at startup; all the bookkeeping, including the cons cells, is kept on the stack. [0] https://github.com/nybble41/prechelt-phone-number-encoding https://github.com/nybble41/prechelt-phone-number-encoding

Zababa 5y ago

If you look at the memory data https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=2144982248 https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFL..., Rust seems like the only one that uses constant memory, and it uses way less than the others. The other thing that I get from this article is that performance is really complex, and never just a function of the language you chose. I'm glad to read articles like that as a junior, I think this will give me a good mental model for performance.

mamcx 5y ago
>and never just a function of the language you chose. I understand your point, but is important to know how NUANCED is this. Performance is MOSTLY driven by the inherent design choices of each language(+ your own!). If you are on Gc, that choice is an impact for everything. Rust have Vectors as base, and lisp have GC-backed linked list. That is another deeeeep choice. But IF you know (or hit the luck!) which are these designs, and understand that not matter which language everyone wanna gotta fast and most common operations (the ones for what THAT lang was designed for!) are fast enough... then all is ok, in average. Is when you go against that design that you see how the illusion crack a little. Then, is all about how much you can workaround about it to recover most of the performance
- pjmlp 5y ago
  Or when one fails to understand what is actually available to them on the toolbox and only look for what is visible at top level. For example, yes Lisps have a GC backed linked list, but in the case of Common Lisp, they also have arrays, stack allocation and deterministic resource management macros.
- Zababa 5y ago
  That is very true, for example Java, even while being as fast as Rust and Lisp, takes way more memory than both of them. My point was more for myself (and maybe other people that haven't heard a lot about performance), as I had very strict ideas about it, but thanks to articles like that I can understand how it's more nuanced. Software engineering and computer science are both really vast and deep fields, but a lot of information is here online, shared freely by awesome people. That means that for a lot of things, being aware of something is enough to make good decisions. These types of articles allows me to be more aware of the nuances of performance (and how complex it is as a topic). For example, if I'm just trying to optimize the speed of my algorithm, and only know Java, Java might be enough. But if I'm trying to optimize my cloud spendings, considering the memory consumption of Java, it might not be the best choice. Comments like yours are also a great way to learn more. I know that linked-lists are really good in Lisp (and OCaml too!), but with other languages there's not often the best choice.

brundolf 5y ago

Implementing a Lisp cons algorithm as-is using a Vec is so far from being apples-to-apples that it makes me question the results of the entire article, despite the fact that things were eventually "optimized" to not do this. Gathering a list by calling cons over and over is only remotely advisable when you're working with a linked-list (which you are, in Lisp). Blindly replacing it with a Vec demonstrates either a total ignorance of CS fundamentals, or a willingness for the benchmarks to come out a certain way. A real "apples-to-apples" comparison would at least have Rust using an actual linked-list for this algorithm. A mutable Vec is more idiomatic and probably more efficient, but cloning an immutable Vec at every step turns O(N) into O(N^2). Note that this isn't Rust apologism: the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. Most languages' go-to structures for holding a sequence have roughly the performance characteristics of a vector. I guess the article at least fulfills its title: "How to write slow Rust code"

phoe-krk 5y ago
> the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. ...or, to be fully honest, a Common Lisp VECTOR that is then CONCATENATE'd with a new element at its beginning. As I said in another comment, this isn't the problem of using a given language - it's the problem of using a wrong data structure for the job.
- brundolf 5y ago
  Exactly. And the fact that it's framed as "well I just wanted a straight comparison, I didn't want to wade too far into idioms and Rust-isms in the first pass" feels disingenuous.
lalaithion 5y ago
The more general view to take from this is that when you program a lot in one language, you get so used to certain performance patterns that you simply write your code in a way that takes advantage of them first try[1]. Peter Norvig's Lisp solution is an optimized solution for Lisp in a lot of little ways. Directly translating an optimized-for-Lisp program into any other language is silly, because you miss out on the optimizations available in that language to an experienced programmer and you lose out doing pointless things which were essential in Lisp.

xondono 5y ago

It might be just the write up, but the article reads like he was playing with the benchmarks until he got a result where Java was faster. I don’t think anything malicious has happened, just pointing out that benchmarking is hard, and changing parameters just to see what happens is not benchmarking. I haven’t gone deep enough into the code and the problem, but it looks like this: What if we swap the Rust HashMap implementation, as they say the standard one I was using applies a cryptographically-safe hash that the JVM doesn’t Is quite a distinction, especially for the latter cases with lengthier phone numbers.

lkey 5y ago

I don't recommend drawing too much of a conclusion from these tests, about anything other than printing in <your language>. Once the algorithm is somewhat optimized, the benchmark is completely dominated by printing to stdout, not the algorithm in question. Pulling from the near the conclusion here, bugaevc finds: "And the measured time reflects how long it take to actually compute the solutions (≈1.6s), not how much time it takes to output/buffer them (≈59s)." source: https://github.com/renatoathaydes/prechelt-phone-number-encoding/pull/1 https://github.com/renatoathaydes/prechelt-phone-number-enco...

kennywinker 5y ago

I got a lot out of this article, thanks! One of my problems with learning rust has been the “draw the f**ing owl” problem. There are lots of tutorials on getting started, and while advanced code is easy to find i have not found a lot of intermediate or advanced code with good explanatory annotations. Great seeing someone take beginner code and rustify it!

mst 5y ago
Right, I really enjoyed it on that basis too. I'm quite amazed how many of the responses are criticising his original code when the whole point of the article is that his original code was n00btastic and he's very grateful to've been helped to improve it and wanted to share.
- igouy 5y ago
  > … his original code was n00btastic… Sorry, but this is at-least the second blog post, in the last week, and previously — "I've discussed the Rust and Julia versions with experts in those languages (—— I know Rust well enough ——, but very little Julia) and no obvious mistakes were found." https://www.reddit.com/r/lisp/comments/osqgqe/common_lisp_still_beats_java_rust_julia_dart_in/h6qd67d/ https://www.reddit.com/r/lisp/comments/osqgqe/common_lisp_st... Before that, on finding the output from his Java program was different than the output from Peter Norvig's Lisp program — "It looks like Norvig's Lisp solution must have a bug: it can't find all valid solutions!" https://github.com/renatoathaydes/prechelt-phone-number-encoding/tree/rust-optimised https://github.com/renatoathaydes/prechelt-phone-number-enco...

mastrsushi 5y ago

By writing anything :^)