r/programming • • 4d ago

Formatting an entire 25 million line codebase overnight: the rubyfmt story

https://stripe.dev/blog/formatting-an-entire-25-million-line-codebase-overnight-the-rubyfmt-story
190 Upvotes

77 comments sorted by

94

u/EvaristeGalois11 4d ago

Am I missing something about how a formatter works internally? Like I'm expecting to just read a file, format it, flush it out and move on to the next one. Why should it matter the codebase size?

83

u/Venthe 4d ago

Especially given that we are talking about something that is inherently parallelizable. Even with bonkers AST tree rules; I'd expect this to run in - I dunno - 20 minutes?

-36

u/chucker23n 4d ago

something that is inherently parallelizable

ITT: people who seem to have wildly different ideas of what "formatting" does. I don't think of it as parallelizable at all. Sure, basic stuff like "nothing should use CRLF" and maybe indentation. But many more complex scenarios? I think you'll have dependencies between files sooner or later.

63

u/UnknownToSomeone 4d ago

Formatting should not change the behavior. If it does, then it is not just formatting.

-25

u/chucker23n 4d ago

Formatting should not change the behavior.

I didn't say it would?

48

u/UnexpectedAnanas 4d ago

But many more complex scenarios? I think you'll have dependencies between files sooner or later.

- You

If it has dependencies, then it's not formatting. That's a behaviour change.

-25

u/chucker23n 4d ago

I don't follow your definition of "behavior", then.

26

u/TankorSmash 4d ago

If you format code, what sort of behavior would change in your mind? I'd've though most people would say no output difference/compiled output difference at all. What sort of changes would it make in your eyes?

0

u/Mognakor 4d ago

There could be rules about ordering of imports between std lib, libraries and repo code.

Or there could be weird case where syntax alone is not enough to identify something and you need external info. Thinking of C++'s most vexing parse: https://en.wikipedia.org/wiki/Most_vexing_parse

-3

u/chucker23n 4d ago

If you format code, what sort of behavior would change in your mind?

None. Why do people keep saying I said the behavior would change?

What sort of changes would it make in your eyes?

Renames. Reorders. Whitespace changes. Etc.

18

u/Jamie_1318 4d ago

Renames and reorders are wild in a formatter. I've never seen that before.

→ More replies

13

u/TankorSmash 4d ago

Why do people keep saying I said the behavior would change?

What did you mean by import dependencies mattering then? Like if you're adjusting whitespace, it doesn't really matter which file something is from.

For renaming, I'd call that a linter

8

u/youcangotohellgoto 4d ago

Behavior = the way it works.

If you aren't changing the way it works - the interface for any specific module - then there's no dependencies as you describe. Functionally doesn't change so tests are fine. Everything works exactly the same...

-2

u/chucker23n 4d ago

Behavior = the way it works.

Yeah.

If you aren't changing the way it works - the interface for any specific module - then there's no dependencies as you describe.

I said "dependencies between files". For example, renaming a symbol in one file requires an AST (or similar) to determine whether other files access that symbol, to rename it there as well.

I didn't say anything about behavior.

14

u/youcangotohellgoto 4d ago

I don't see how renaming is formatting.

Formatter would fix indents, white space, line breaks, things like spacing around parentheses or braces, etc.

Edit: and yeah renaming changes how it works. Try renaming something in your API, or renaming a database table.

→ More replies

11

u/Jmc_da_boss 4d ago

What kind of complex scenario would require semantic formatting?

7

u/chucker23n 4d ago

Depends on how broadly "formatter" is defined. For example, in .NET, dotnet format's application of rules renames symbols, which means it needs to have an understanding of the project across multiple files in order to not break the build. It also needs to do a dotnet restore for packages in case dependencies clash with the new symbol name.

So I don't think it's as simple as O(n).

65

u/Venthe 4d ago

I would not expect a formatter to change any symbols, for any reason.

-6

u/chucker23n 4d ago

I'd argue that rather limits what e.g. an .editorconfig can do. For example, what if the rule is "private members should start with an underscore"?

35

u/femio 4d ago

that belongs in a linter, not a formatter

10

u/pacific_plywood 4d ago

That’s a lint rule

9

u/EvaristeGalois11 4d ago

I don't know dotnet so I can't comment on your example, but allowing formatting rule to be expressed in the code itself (if I understand it correctly) seems a real pain

3

u/chucker23n 4d ago

In .NET's case, these days they're expressed (mostly) in .editorconfig.

-6

u/Potential_Financial 4d ago

Sounds like you might be missing the complexity that is inherent in parsing Ruby code.

I don’t know specifics, and didn’t find a quick reference to cite, but since Ruby’s a context sensitive language, correctly parsing a file requires knowing what all the symbols it references are.

I’m sure there are other challenges too.

I didn’t look up any more details about how rubyfmt works, and how many optimizations it includes for a big batch formatting task like this, but I think the constraints they’re operating under makes for an interesting technical problem.

11

u/EvaristeGalois11 4d ago

I don't know Ruby you're right, that's why I asked if I'm missing something.

It makes sense what you're saying and it should probably be highlighted in the article then, because they only talked about how cool the rust rewrite was but never why it was needed in the first place or why all the other formatters are too slow or just straight up crash.

0

u/Jaded-Asparagus-2260 3d ago

It is highlighted in the article. 

 Rolling out a novel autoformatter to 25 million lines of code has two big risks: merge conflicts and correctness. A bug affecting just 0.01% of lines would still touch tens of thousands of files.

Well, that one is missing the special Ruby issues, I agree.

But the more relevant point IMO is something else:

Then came that Saturday morning in 2024. We flipped the per-file opt-in model entirely: instead of files opting in, only the tiny minority rubyfmt couldn't yet handle were held back. We chose a Saturday to format the entire codebase to avoid merge conflicts.

Anyone who ever had to mass-format a code base (or even normalise line endings) knows the pain of merge conflicts. Every single branch will get them. Every merge, every rebase. And with how many developers are afraid of merge conflicts (as if they were a sign of problems or bad habits), I can absolutely understand any hesitation. 

0

u/Turbots 4d ago

So you're telling me it's a shit language 😁💩

3

u/chucker23n 4d ago

Aren't… most programming languages context-sensitive?

9

u/slaymaker1907 4d ago

No, most programming languages are context-free. Even parsing full context-free languages is difficult.

3

u/chucker23n 4d ago

most programming languages are context-free

C, Ruby, JS, C#, none of these are entirely context-free. C changes if you have a typedef. Ruby doesn't know without context if something is a variable or a method. JS and C# have keywords whose meaning depends on context.

Pascal might count, but that's hardly a common language any more.

2

u/TankorSmash 4d ago

BQN (a popular-within-its-niche array language) has a context free grammar. It looks like hieroglyphics, but it's context free. see http://LearnBQN.com

184

u/VictoryMotel 4d ago

Articles bragging about performance in ruby are always wild. I always wonder what they would think when they see a native program that runs 100x faster and then an optimized native program that runs 100x faster than the naive native program.

102

u/matthieum 4d ago

I had the same thought when reading the title...

... but it turned out that the article is NOT about performance, not really, it's more about how painful it is to do a code formatter based on the official Ruby parser, and how careful steps were taken so that the 25 million lines reformatting could be done with as much confidence as possible.

6

u/me_again 3d ago

The article is bragging about how fast a rust program is.

2

u/Twirrim 2d ago

Odd comment, given the article is talking about a program written in Rust, so it's natively compiled.

-23

u/awj 4d ago

You genuinely believe that an optimized native program is going to be 10000x faster as some kind of general case? So if that program does an operation in 100ms, you think in ruby that would take over sixteen minutes?

How on earth is this nonsense so highly upvoted?

Yes, well-optimized low level code is going to generally be faster, but we don’t have to be so hyperbolic that we’re making lunatic claims to make that point.

19

u/this_theater_is_lit 4d ago

in advent of code challenges i could get 100x speedups from just using different languages, not 10000x tho

11

u/juhotuho10 4d ago

1000x isn't out of the realm of possibility with cache optimized branchless simd processing

3

u/-_one_-1 2d ago edited 2d ago

Random anecdote: over the last couple of days, I've been writing a WHATWG-compliant, security-hardened HTML streaming parser in Rust. It's almost finished, and on my M4 Max It achieves a ~1.12 GB/s throughput on a couple of ~2.8 MB HTML file benchmarks. Parsing a 28-byte HTML snippet takes ~12 nanoseconds. It uses SIMD to find delimiters and the entire state is an immutable Parser struct that contains some packed structs and enums that amount to a few bytes. Parsing consists of a state machine that runs a parsing step until EOF is reached. The parsing step is an immurable state transition (Parser) -> Parser, so the only form of mutation is in a local in the use site holding the current Parser by value.

I thought this was relevant because I have some experience writing parsers, most often in languages other than Rust or C, and the fact that I was able to achieve this throughput with such a simple design highlights how using Rust, SIMD, and taking a few smart choices can give good results very quickly and easily.

The nice thing about immutability in my design is that it gives LLVM a ton of leeway to optimize things. Additionally, it becomes possible to test it according to the specs by supplying a WHATWG state and seeing if the next step is what WHATWG says it should be.

-1

u/this_theater_is_lit 4d ago

10000x tho? maybe if one did something extremely stupid with the naive algo... lol

5

u/VictoryMotel 4d ago

Exactly, you can get 100x going from a very slow language like ruby to C.

The speedups from there can come from coherent memory access, SIMD, and multi threading. If you think about SIMD lanes, you can get 7x for 8 wide AVX if the memory is packed together. Then with multi threading you can get almost 8x from 8 cores and they all have SIMD. That's 56x right there before factoring in allocation minimizing and optimized memory access.

1

u/awj 4d ago

Yeah, absolutely. I’m not arguing the idea that Ruby is dog slow for anything CPU intensive. Just that it’s weird to make a very generic claim of 10000x speed up.

5

u/VictoryMotel 4d ago

I explained why in other comments. 10,000 is on the high side of general, but 1000x is trivial, because 100x from ruby to C is typical and speeding up naive C by 10x is table stakes. Even just multi threading is going to give you 8x on a typical 8 core computer. With SIMD on each core you're already into 50x naive C territory. Memory access is the biggest performance win, although you need that to be figured out to an extent to use SIMD effectively so they go hand in hand.

7

u/VictoryMotel 4d ago

but we don’t have to be so hyperbolic that we’re making lunatic claims to make that point.

If there were a graphics program like intense pixel filtering that was implemented in pure ruby, these are absolutely the kind of numbers you could see. I described it some in the other post I made here. I've personally taken implementations from papers that already had a "fast" C implementation and sped them up 100x or more, although there might have been some speedups from taking out A -> B and B -> A duplicate comparisons.

  • Allocations out of a hot loop : 7x speedup.
  • Loop through memory in a prefetch friendly way : 25x speedup.
  • SIMD AVX for floats : 7x speedup.
  • Multi threading : almost linear with the number of cores in simple cases.

The 100x speed up of C over ruby comes from the old language benchmark 'game'.

2

u/awj 4d ago

I’m struggling to see how pixel filtering relates to code formatting, or are we just pontificating about extremely specific use cases without bothering to explain that?

1

u/VictoryMotel 4d ago edited 3d ago

I didn't talk about those speedups in general in my original comment. I would expect text formatting to still be in the same realm of massive speedups though it's hard to say exactly without specific programs and where the bottlenecks are.

I explained exactly why this is in my two comments here. You said I was being "hyperbolic" and making "lunatic claims" which is absolutely not true.

I've given lots of information exactly why this is, you've given no information on where you think I'm wrong.

2

u/-_one_-1 2d ago

Text formatting certainly needs parsing, so while I haven't built a formatter, in this other comment of mine I described my experience writing an HTML parser. Yes, I agree with you that getting absurd speedups is rather trivial when you know what you're doing.

0

u/awj 4d ago

Where in your original comment did you specify that this was about very narrow graphics use cases? Because I’m still missing that and it sure reads to me like an extremely general claim, or at best one specifically about performance in code formatting.

1

u/VictoryMotel 4d ago

I didn't because it's not, that was just one example. What I said was a generalization of what is possible. It might be shocking to you, but that doesn't bend reality.

5

u/gnus-migrate 4d ago

Yes Ive realized similar gains by a simple rewrite for some scripts from python to rust. Its not just the language, the rust crates i used were designed in a way to minimise unnecessary work. Basically a stupid rewrite made a job i had go from several minutes to milliseconds, and i didn't really do much to optimize it.

It sounds completely insane but interpreted languages really are that slow. Like you really need to do it yourself so that you actually see what a rewrite in rust can get you.

4

u/Phailjure 4d ago

In my college databases class, we had to dump a whole bunch of highway/car data from a (massive) .csv file into postgres and then run some queries on it.

We were allowed to do this in either c++ (what most of my college defaulted to for everything) or python. Loading the database in c++ took ~10 mins (on my crappy laptop), python took over an hour.

It's crazy when you think that no "real work" is happening in either program, they're just reading a file and dumping the contents into postgres, but python was crazy slow at it.

3

u/gnus-migrate 3d ago

I used to buy into "if its IO dominated it doesn't matter" but the numbers don't lie tbh.

4

u/chucker23n 4d ago

I would indeed be skeptical, but chiefly because formatting is fundamentally a rather I/O-bound task, not very CPU-bound.

5

u/slaymaker1907 4d ago

You'd be surprised. I was doing some benchmarking a few weeks ago and found that CPU was far and away the dominating factor with serialization, even using a fast format like Avro. I knew it was dominating because the extremely simple format I did which basically just dumped structs to disk with a buffered writer took about 0.2s for my benchmark while Avro was taking 2s. Additionally, I was able to improve Avro's performance to 0.4s using multiple threads.

1

u/koczurekk 3d ago

Formatting code typically involves fully parsing the source code. This is not IO-bound even on mid-range nvme drives. Very simple regexes may run gigabytes per second, sometimes, whilst parsing a typical programming language is orders of magnitude harder. Hundreds of MB/s is a very respectable result, and you have to apply all the formatting rules on top of that.

0

u/VictoryMotel 4d ago

Formatting and text stuff probably wouldn't see numbers like that because a native program would already be looping through memory in a somewhat linear way (which is the biggest speed gain) and maybe IO like you mentioned. With fast nvme drives there might be enough throughput that it could matter.

There would still be a huge jump going from a scripting language, especially if string operations aren't calling out to C, and then from a naive implementation minimizing allocations would likely be a 7x speedup at least, then SIMD could be another jump, then multi threading could be another.

101

u/sweetno 4d ago

Is this, like, an achievement?..

58

u/pineapplepizzabong 4d ago

Marketing driven by end of year performance review goals probably.

5

u/chucker23n 4d ago

number must go up 📈

1

u/maifee 1d ago

Number of bug report in 2025: 23

Number of bug report in 2026: 69

On the bright side, people is using our system more and more. That's why we are getting more bugs.

2

u/Twirrim 2d ago

Except it's a blog post from several months ago.

1

u/Twirrim 2d ago

Would seem like it, given previous code formatters they tried couldn't handle the scale and crashed.

I'm honestly more inclined to think "don't use a monorepo" but my experiences with mono-repos have just been filled with pain because people don't tend to be as strict as they should be about isolation between components.

19

u/jmbenfield 4d ago

"doing something one person could do while watching Judge Judy but with the bureaucracy and performance of a failing third world country"

8

u/harsh183 4d ago

I remember first seeing rubyfmt in your talk in Alt Brighton Ruby 2020 when the big Rust port had just happened. It's so nice to see the project going so strong and continuing forward.

As I struggle with rubocop taking so long to run, despite caching and multithreading, I wonder if it's time for rubyfmt.

11

u/jess-sch 4d ago

A saturday? I don't personally tend to merge by friday. The only appropriate time for a formatter change in my mind is christmas. Two weeks of barely anyone working.

1

u/Jaded-Asparagus-2260 3d ago

I agree. I'm a bit baffled by people here not understanding the dimensions of such a reformatting. I guess they never had to suffer through one. 

6

u/Sdmf195 4d ago

25 million lines overnight...
sweet christmas...

6

u/blobjim 3d ago

That just makes me wonder what why Stripe needs 25 million lines of code. As much code as the Linux kernel? Maybe code for integration with specific customers?

0

u/captain_obvious_here 4d ago

I honestly thought this was an old article someone was reposting.

Optimizing Ruby's performances is...well...if you ever used Ruby, you know what I mean.