Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How we made a Ruby method 200x faster

campsite.com

Post reply on HN
Print view View original

31–40 of 48 posts

Re: How we made a Ruby method 200x faster

#31

Post by jesse__ »

jesse__ wrote: post #28
franciscop wrote: post #27

I've flamegraph-debugged JS code from time to time, and it usually feels a lot more of a craft and "educated guesses" than the vast majority of programming things I do. I usually only get down to it when there's an actual perf problem so YMMV, but I'm curious, do I do JS flamegraph debugging wrong, or is it something like this for everyone? - 20% of the times you get lucky and find a very easy win that speeds up thin…

I do low level systems programming, so pretty different from JS-land, but I feel the techniques you should apply when doing optimization generally apply at any level/language. 0) algorithmic improvement. Obvious shit like do a quick sort instead of bubble sort (assuming N > 64, or whatever), not doing unnecessary work in a hot loop, etc 1) reduce memory footprint. The slowest part of your program is almost always jus…

EDIT: I forgot to mention that for tight performance, avoid branches. This means ifs, switchs, loops, goto, etc. Sometimes you need branches, but mispredicted branches can be extremely costly, causing pipeline stalls and flushes. This is why using a static loop is important; so the compiler can unroll it and not use a branch.

I also should mention that I hate flamegraphs. They only give you a bare minimum amount of information for doing performance work. I'm not sure of a good JS profiler, but what you want to be able to do is mark up the sections of code you want profiled, instead of the profiler taking random samples and squashing them all together. Look at the tracy profiler for an example

Re: How we made a Ruby method 200x faster

#33

Post by swatcoder »

franciscop wrote: post #27

I've flamegraph-debugged JS code from time to time, and it usually feels a lot more of a craft and "educated guesses" than the vast majority of programming things I do. I usually only get down to it when there's an actual perf problem so YMMV, but I'm curious, do I do JS flamegraph debugging wrong, or is it something like this for everyone? - 20% of the times you get lucky and find a very easy win that speeds up thin…

Keep in mind that there are many layers of complex systems between your JS code and what'll end up happening on your system when it's run.

The code defines what the state should look like after its done executing. It expresses your intent. But that code gets transformed several times on the way to being executed and then the hardware can apply mang different possible approaches to executing it when the time comes.

Moreso every year, many of those software transformations, as well as the hardware's execution technique, are quite aggressive about revisiting your program's intent with optimizations (of some kind) that make sense within that context.

The upshot is that the farther you are from your hardware, the more of these layers there are between your code and its execution, the less influence and insight you have over what actually "physically" happens during execution.

When it comes to profiling and optimization of high-level programs like those written in Javascript, this means that it can ve somewhere between hard and impossible to predict how your code changes will actually impact performance.

Radical algorithm redesign can often yield salient diffferences that feel largely predictable, but smaller "precision" changes are often going to be a crap shoot. All those layers between you and the hardware were making optimzations already anyway, and your "precision" change may just as easily confound those existing optimizations as well as it might trigger some other. The results are tricky.

This is even true in lower-level code, where we're encouraged to do things like inspect compiler output on godbolt or in our compilation output and always confirm our expectations with a profiler (which often proves our guesses wrong). But it's all that much more pronounced in high-level ones.

So ultimately, yes, assuming your prevailing algorithms are generally optimal, profiling and optimization is almost always going to feel like a guess-and-test process. But that's okay, because you can test and those tests are usually (not always) telling you if you've made a meaningful difference or not.

Re: How we made a Ruby method 200x faster

#34

Post by esprehn »

the_other wrote: post #23
cluckindan wrote: post #13

This should have been obvious before the fact to anyone who understands how CSS selectors work in browsers. As in, they are matched right-to-left, which implies that a selector like ”p a” first selects all the nodes, and for each of them, it then traverses up the DOM tree until it encounters a node (selector matches) or the root node (selector doesn’t match). That said, the traversing shouldn’t happen for plain tag s…

Is that really how it works in browsers and other rendering engines? Intuition suggests to me that it wouldn’t start with CSS and then find all the matching DOM nodes. I would expect it started at each DOM node and then found the CSS rules which might apply. So “I’m adding an A to the tree; what are all the CSS rules with or A or * at the rightmost token; which of that set applies to my current A; apply the rules in…

There's three different modes of running a selector in typical browsers:

  (a) Element#matches
  (b) Element#querySelector(All)
  (c) By the engine for updating style and layout
The GP seems to be talking about (b), but even then browsers are checking each element one by one not advancing through the selector state machine in parallel for every element. (There's one exception in the old Cobalt which did advance the state machines IIRC).

(a) and (c) are conceptually very similar except that when doing (c) you're checking many elements at the same time so browsers will do extra upfront costs like filling bloom filters for ancestors or index maps for nth-child.

In TFA they're doing .matches() which I would expect to be slower than a hash map lookup, but for a simple selector like they're doing (just tag name) it shouldn't do much more then:

  (1) Parse the selector, hopefully cache that in an LRU
  (2) Execute the selector state machine against the element 
    (2.1) Compare tagName in the selector
Apparently Nokogiri implements CSS in a very inefficient way though by collecting ancestors and then converting the CSS into xpath and matching that:

https://github.com/sparklemotion/nokogiri/blob/e8d30a71d70b2...

https://github.com/sparklemotion/nokogiri/blob/e8d30a71d70b2...

I'd expect that to be an order of magnitude slower than what a browser does.

Re: How we made a Ruby method 200x faster

#35

Post by mewpmewp2 »

I do wonder if the refactor will actually be better. The node by names seems like a scarier exceptional case that forces you down the road compared to when or whatever case being more straightforward. I think the OOP would work better if each node handler defined their own matcher.

Re: How we made a Ruby method 200x faster

#36

Post by bastawhiz »

chikere232 wrote: post #11

The title kinda glossed over the fact that they started out with working, fast code, and then broke it. Sure, their fix was faster than their most broken version, but it's less impressive than starting with slow code and improving it.

They said they made the change because the code was starting to become hard to maintain. That's not a terrible reason for refactoring.

Re: How we made a Ruby method 200x faster

#37

Post by ngcazz »

viraptor wrote: post #4
Alifatisk wrote: post #2

That's a huge improvement but damn, the fixed code didn't look any better in my eyes. Going from HANDLERS = [ Text, List, ListItem, Code, # ... ].freeze to HANDLERS_BY_NODE_NAMES = [ Text, List, ListItem, Code, # ... ].each_with_object({}) do |handler, result| handler::NODE_NAMES.each { |node_name| result[node_name] = handler } end.freeze

I'd go with this since it's not performance critical code. Not sure if it's that more readable, but I like it better: BY_NODE_NAMES = HANDLERS.map {|h| h::NODE_NAMES.map {|n| [n, h]} }.flatten(1).to_h

I think we can go harder on the std lib :)

  HANDLERS.flat_map { _1.node_names.index_with(_1) }.inject(&:merge)
(nb: assuming there exists a `.node_names` to expose the constant... just because I like always using method calls)

Re: How we made a Ruby method 200x faster

#39

Post by notjoemama »

bastawhiz wrote: post #36
chikere232 wrote: post #11

The title kinda glossed over the fact that they started out with working, fast code, and then broke it. Sure, their fix was faster than their most broken version, but it's less impressive than starting with slow code and improving it.

They said they made the change because the code was starting to become hard to maintain. That's not a terrible reason for refactoring.

I think they were referring to the degree of speed up.

Re: How we made a Ruby method 200x faster

#40

Post by bastawhiz »

notjoemama wrote: post #39
bastawhiz wrote: post #36

Earlier quoted context omitted.

They said they made the change because the code was starting to become hard to maintain. That's not a terrible reason for refactoring.

I think they were referring to the degree of speed up.

The degree of speedup is the refactored code being fixed to not be slow.
Post reply on HN