Avoid expensive clones in loop

[spenserblack]

The worktree stack and outcome of attr matches is getting cloned per path/entry, which, as @Byron pointed out in #200, is not the intended usage. Also, a thread-local repository shouldn't be created per-path.

This will almost unavoidably change some immutable values to mutable refs, which will be reflected upstream in the implemented trait. This will count as a breaking change due to the public trait's required method signatures changing.

---

Edit 2023/10/09:

Perhaps a FileSource could implement a method that returns a mutable thread state.

[spenserblack]

So, just skimming the docs, one of the sins of these calls to .clone is that these values cache data, and I assume is mutable so that it can expand the cached values only when needed.

[Byron]

The title makes gix types very special and particularly sensitive to clones, even though I think there is a general truth here: Clones for the purpose of making something mutable are definitely to be avoided, especially in a tight loop.

I believe there is a reference implementation that should be consulted in terms of performance to validate there was no regression. I'd use hyperfine for that.

hyperfine -N --warmup 1 gengo-known-good /path/to/latest/target/release/gengo

Performance is part of the value proposition and thus I think it's critical to protect it from regressions. Criterion can also be used for microbenchmarks, it will neatly display the difference between runs so regressions, or improvements, become evident quite clearly.

[spenserblack]

The title makes gix types very special and particularly sensitive to clones, even though I think there is a general truth here

Sorry if I made it sound like gix is a special case -- I just wanted to emphasize that the .clones are basically working against gix's performance optimizations (if I understand correctly). If you have a recommendation for a better title, I'll happily change it 🙂

Thanks for recommending hyperfine!

[spenserblack]

Results of hyperfine -N --warmup 1 /usr/local/bin/gengo6 /usr/local/bin/gengo:

Benchmark 1: /usr/local/bin/gengo6
  Time (mean ± σ):      2.486 s ±  0.019 s    [User: 4.588 s, System: 0.248 s]
  Range (min … max):    2.458 s …  2.517 s    10 runs
 
Benchmark 2: /usr/local/bin/gengo
  Time (mean ± σ):      5.691 s ±  0.036 s    [User: 5.741 s, System: 1.097 s]
  Range (min … max):    5.658 s …  5.776 s    10 runs
 
Summary
  '/usr/local/bin/gengo6' ran
    2.29 ± 0.02 times faster than '/usr/local/bin/gengo'

Where gengo6 is an installation of gengo 0.6.0 (14fb5c3) and gengo is gengo 0.7.1 (4f97717). Both run on a shallow clone of linux at torvalds/linux@633b47c.

[Byron]

Thanks for the numbers! There definitely is a lot of performance to be had by avoiding clones in a tight loop.

Sorry if I made it sound like gix is a special case -- I just wanted to emphasize that the .clones are basically working against gix's performance optimizations (if I understand correctly). If you have a recommendation for a better title, I'll happily change it 🙂

There is no gix optimization to worry about. It's generally wrong to clone in order to get something to be mutable (if it's not also Copy). If types are not copy, clones are expensive.

[spenserblack]

Got it, updated the description. But these gix types aren't caching anything? Given that the APIs getting used required mutable references, I assumed some sort of caching of values on-demand was happening.

[Byron]

But these gix types aren't caching anything?

They have state, but it's not a cache. Maybe it's just terminology though, as one can probably see all state as cache if one wanted to as long as one is able to set the state to the point where it's needed to get the correct response, albeit much more expensively.

[spenserblack]

Got it, thanks! Yeah, I could've used clearer wording -- state would be the more appropriate word.

[spenserblack]

Note-to-self: I'm not really fond of mut bubbling up from the file source all the way to the Gengo struct. So, instead of analyze(self) + self.file_source, analyze(self, mut file_source) might be more manageable.

[spenserblack]

@Byron sorry for bugging you again, but I was looking at the gix::parallel docs.

Which of these is new_thread_state?

• new thread state
• new thread state

I was reading it as the former for a while. That is, a state that is created once per thread. But I'm thinking that interpretation was probably incorrect, and as a result I was misunderstanding the intent of the code you authored (#200 (comment)).

[Byron]

It's state created once per thread and passed mutably to consume. I hope that clears this up at little.

[spenserblack]

Got it. Yeah, with your comment and by reviewing the source code I think it's clear now. My naive and incorrect assumption was that a thread was spawned per item in the slice, when in reality gix::parallel was producing multiple threads that each iterated over the same slice. Threads that iterate, not iteration that spawns threads. A beautiful piece of code!

Since a lot of the logic isn't specific to gix, I wonder if you'd be interested in moving gix::parallel to a separate crate? Seems like the Rust ecosystem could benefit from these utilities being more generally available.

[Byron]

Since a lot of the logic isn't specific to gix, I wonder if you'd be interested in moving gix::parallel to a separate crate?

That may sound harsh, but the answer is: "Definitely not" :D. The reason for this is that it's a couple of lines that can easily be copied to where they are needed, along with the adjustments that are typically needed as well. I keep modifying how these utilities work and experiment with them until maybe they turn out to remain stable because they work for my usecases.

I'd consider them basic and (except for the slice-based version of it) potentially problematic as the chunk-based forms don't do work-stealing. Other approaches can be better, but gix can't use rayon because I don't understand it and I don't trust it - but at least on paper it pretty much does what one wants :).

The beauty here really is that thanks to Rust it's easy to come up with simpler primitives that still work well enough most of the time, while letting them fit on a screen. There is also no Sync bound which makes them easier to use at least in the gix code-base, Send + Clone perfectly maps to thread-local state which gix encourages. But with that said, I'd even recommend to write your own even if it looks similar to the the one in gix-features::parallel - go through the paces and when done you know why I am writing this :).

[spenserblack]

The reason for this is that it's a couple of lines that can easily be copied to where they are needed, along with the adjustments that are typically needed as well.

You're reminding me of is-even and is-odd 😆
https://www.npmjs.com/package/is-even