6 ms·
Spending too much time optimizing for loops
- o11c 2y agoI'm not sure how useful this is for interpreters in general, given the frankly bizarre design decisions. My normal rant about bad interpreter design assumes things not seen here.
- kragen 2y agoare you talking about the design decisions that define smalltalk or something else
- o11c 2y agoI'm not talking about the inner language semantics (which mostly don't matter, other than what optimizations they allow - particularly static typing and SROA), but the implementation of the interpreters themselves.
- kragen 2y agowhat do you think is unusual about the interpreter implementation? from what i read of the post (admittedly not all of it) it sounds like a fairly by-the-book smalltalk-80 blue book thingamabob?
- moonchild 2y agoi saw this last week and was incredibly confused. aside from being naive it's totally overfit where general approaches are very well known??
- brabel 2y agoYou can get a Phd by doing stuff like this?? I do that kind of thing for fun after work on my hobby projects, and at work I've spent weeks speeding up a single HTTP request path.
- FrostKiwi 2y agoHighly specialized topic of computer science, in a tough challenge with no easy solutions and new discoveries documented for anyone to follow in the future. I would be sad, if you couldn't get a Phd for stuff like this.
- kragen 2y agotheoretically your result has to be (1) novel and (2) published with such a good explanation that people understand both the result and what's novel about it, as well as how to reproduce it, but yes. the difference between tinkering and science is documentation, and it needs to be public and conscious of the existing discourse to be scholarship
- gwervc 2y agoThe biggest difference is gate-keeping by peer review, which is quite random. Reproductibility is a meme in most fields.
- jvanderbot 2y agoEven in random noise, with enough samples the signal is measurable. Thus - publish or perish.
- kragen 2y agoi knew someone was going to reply by pointing out that academia often fails to live up to the standards of scholarship and, where applicable, science. but that's sort of missing the point; i was describing the standards, not how the existing institutions' performance measures up to them
- brabel 2y agoNo offence, but what's novel in this post??? I found it pretty basic, or?
- OJFord 2y ago
- larsga 2y agoFWIW, my experience with JSLT https://github.com/schibsted/jslt/ https://github.com/schibsted/jslt/ was that I first wrote an AST interpreter. Then I and another person independently wrote bytecode interpreters, but the AST interpreter remains faster than both. It may be that the JVM is simply better at optimizing one type of code than the other.
- brabel 2y agoIf you're writing the interpreters in Java (or other language compiled to JVM bytecode) your code itself is going to be interpreted and JIT'd on the go by the JVM, so it's really difficult to come up with real optimisations to your interpreter. In my experience, the JVM "likes" dumb code: direct, without abstractions on top. Use static final methods for everything, no inheritance, avoid memory allocation (though the JVM is insanely good at optimising small, short memory usage). In a bytecode interpreter you may be tempted to use "proper" type hierarchies with Ops represented by interfaces and things like that. Instead, using an array of objects of the same type which can hold the "variants" (basically, C-style OOP without vtables) of each Op is what makes things go from slow to fast. The code looks very non-idiomatic for Java, of course, but with care can be made pretty readable.
- robinei 2y agoIdeally arrays of primitive values like `long` to store the bytecode represenation for proper good performance. Then use bitwise manipulation to access "fields"
- bruce343434 2y agoAt this point, why not just use C or C++ since you are already writing it like that? Gets rid of the whole middleman.
- gjadi 2y agoBecause you get all the nice tooling around the JVM + safety of running inside the JVM. See 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://news.ycombinator.com/item?id=24895395 https://news.ycombinator.com/item?id=24895395 > An improvement can be discussed in the morning, and be implemented, tested and released in production in the afternoon.
- bearjaws 2y agosemi-related, recently started doing a "leetcode.com" challenge every morning with my coffee. I am appalled that the top 150 interview questions are 80% iteration avoidance (if you are aiming for good timing). My experience has always been the problem is how you handle API calls, organize queries, etc... I have maybe 5 times in my career been like 'oh wow we need to avoid this for loop'. Then of course there is managing complexity...
- gizmo 2y agoWhat this blogposts gets at, indirectly, is optimizing "Zero cost abstractions". In C++ there are many constructs that when translated directly to machine code would result in a severe performance penalty but clever compilers can remove this overhead. (In simple programs. When zero cost abstractions get stacked on top of each other compilers give up and performance craters.) In languages like Smalltalk Everything Is An Object and instead of function calls messages are sent between objects. It's very elegant. It's up to the compiler to figure out that "1 + 1" doesn't actually require object allocations and message :+ dispatch. Instead all these abstractions can be stripped away so you end up with a single machine code instruction for the addition. In practice this is absolutely hopeless and the compiler will not be able to transform code that is dynamic in theory but static in practice to correct and efficient machine code. This is for two reasons. 1) Language semantics. If you have multiple threads running then one thread can rewrite the code running on another thread. This means the compiler will be hamstrung in the assumptions it can make about even the most simple for loop. Either you must actually send messages for every integer addition because another thread might be listening to those messages or you disallow multi-threading. In either case your performance will be abysmal. 2) Wide instructions. Modern CPUs can do much work in parallel thanks to SIMD. In a world where every integer is a heap object you have no chance of SIMD optimization. It's instructive to look at javascript and python. Javascript engines are much faster than python engines because Javascript doesn't do threads. This means the compiler can do tons of static code analysis. No such luck with Python. If you want to go fast with Python you use numpy, which just calls out to C. Here too the optimizations become possible because the language semantics that are holding optimization efforts back are disregarded once the Python code calls into C. Most of the code we write in practice is pretty static. Dynamic features like virtual function calls, type introspection, and run-time code generation can be added to static languages without much difficulty. On the other hand, it's extremely hard (if not impossible) to get even 10% of the performance your computer is capable of using a highly dynamic language. In practice you don't even get 1%. I know this is an unpopular message but many people have worked hard at making slow languages fast for decades now and it's just not happening.
- brians 2y agoI was all set to defend Scheme, which has several extremely high performance implementations—and then realized you probably just meant Smalltalk, an entirely different language, and picked the wrong 1970s minimalist language starting with S.
- diffxx 2y agoPremature optimization is the root of all evil. Instead of optimizing the performance of the interpreter, they should optimize the language semantics to be fast by default.
- pipeline_peak 2y agoAn engineer accepts the given conditions and finds a way to work within those boundaries. They don’t pine over things outside their control.
- deleted 2y ago[deleted]
- Thorrez 2y agoIs this pushing a stack element for every loop iteration before starting the loop execution? If there are a ton of iterations, won't the stack overflow?
- Frieren 2y agoI see that I am the only one bothered by the title. Optimizing for X is a very common expression, so I read it as "optimizing for loops" as is adding more loops instead of the correct "optimizing for-loops". Or am I the only one?