9 ms·

Writing a competitive BZip2 encoder in Ada from scratch in a few days (2024)

110 points by etrez 1y ago

See also part 2: https://gautiersblog.blogspot.com/2025/07/writing-bzip2-encoder-in-ada-from.html https://gautiersblog.blogspot.com/2025/07/writing-bzip2-enco...

rustcleaner 1y ago
Why did Mozilla reinvent the wheel with Rust when we had Ada/SPARK?
- Jtsummers 1y ago
  SPARK 2012 was what made SPARK viable for a broader audience. Earlier versions of SPARK were not really properly integrated into Ada (SPARK annotations were in comments). SPARK also restricts what is expressible to what is provable within SPARK (which expands over time), this has some important consequences for concurrency and parallelism (using the "concurrency is not parallelism" distinction). So it would have been hard for Graydon Hoare to use SPARK 2012 in 2006 when he started on Rust, and the limitations around concurrency in SPARK 2012 would have been a non-starter for the objectives of Rust as adopted by Mozilla.
- steveklabnik 1y ago
  Glibly, because they’re not the same language. I don’t think I’ve ever heard Graydon comment on Ada specifically, but early Rust was very different than today’s Rust. Funny enough, I’d argue that early Rust was much closer to Ada than the Rust we ended up with. One thing that makes Ada and current Rust different is that Ada does a lot more checks at runtime than rust does, and is more okay with features that have more of a runtime than Rust is. Another is that Ada doesn’t guarantee memory safety at compile time, or at least, it did not at that time. I believe that with the new Spark features that are inspired by Rust that recently landed may bring parity here, but I haven’t had time to investigate those yet. But really, they're just very different languages from each other. There's no reason they can't coexist.
danbruc 1y ago
For those only having a quick look, the charts do not have the y axis start at zero, the differences are much smaller than it looks.
- Sesse__ 1y ago
  Also, they seemingly already had a BWT lying around (which is seemingly not counted in “from scratch in a couple of days”), and there is no mention of speed.
  - vintermann 1y ago
    He didn't specify that the demo of BWT was in Ada, or his own.
  - sltkr 1y ago
    It seems like author means his implementation is competitive in terms of _compression ratio_ only, and this is achieved in the final Huffman encoding step. From that perspective the BWT implementation isn't very interesting because the BWT is deterministic, so the effect on compression ratio doesn't depend on which implementation was used.
- etrez 1y ago
  The data in question cannot be compressed to zero, or close to zero, by far.
tombert 1y ago
I know the history of why Ada failed, but it always seemed like such a neat language that shouldn't have failed. It seemed like it should have been the standard for a lot of desktop applications for the 90's and 2000's.
- steveklabnik 1y ago
  I am curious, knowing that history, why do you think that it shouldn't have? I have my own thoughts that I'd be happy to share, but I don't want to spoil your opinion with them. (This goes for basically anyone who's interested in talking about it, I think it's a fascinating bit of history.)
  - tombert 1y ago
    I just feel like it emphasized safety in a way that C doesn't, while still being fairly high performance. It always seemed like a neat language.
    - steveklabnik 1y ago
      Gotcha, thanks :) I wouldn't disagree with either of those things at a high level, but I think in practice, the details matter, and it's more of those details that led to the present state than the high level goals, which certainly were laudable.
    - fsckboy 1y ago
      it's not like we didn't know about safety back then, but computers were slow, memory was limited, compilers had to be small, optimization was rare, and C was screamingly fast. At the same time, when major compiler vendors couldn't even get their Ada compilers out the door in project overruns measured in years, Mitch Kapor's 1-2-3 was written and took over the spreadsheet market (dethroning the incumbent Visicalc) and it was written in assembler, not even C, and barely had memory to spare on user machines (memory? there was barely address space left to spare). The tradeoffs were authentic, and there was zero enthusiasm for Ada among programmers or entrepreneurs looking to get products launched. The mainframe world could have been different but the personal computer software market was exploding in a way larger systems never did. (oh and let me add, all the undefined behaviors back then were very clearly defined (perhaps over a small field of options) and extremely useful, and should have been left that way; shoot out a compiler warning or error if they get your panties in a bunch)
whartung 1y ago
Well that was disappointing. I was hoping to see a discussion about writing a zip encoder in Ada. How the language was used, values of the language for this kind of work. How it’s easier or harder to do. Maybe a bunch of Ada source code. Simply as one who does not use Ada I had hoped to be a bit more informed about it.
- andsoitis 1y ago
  Bottom of page links to the sources: https://github.com/zertovitch/zip-ada https://github.com/zertovitch/zip-ada
- etrez 1y ago
  Thanks for the feedback. Multiple posts are planned on that topic. For parts 1 and 2 (so far the only ones existing) I preferred explaining the context and the remarkable simplicity of the BZip2 format. In part #4, I will try to show why the customisable types in Ada fit so well compression software. Be patient: writing articles about writing software takes much more time than writing the software itself! In the meantime, there is a short preview of that in recent presentations - notably FOSDEM 2025: https://fosdem.org/2025/schedule/event/fosdem-2025-5148-advent-of-compression-writing-a-working-bzip2-encoder-in-ada-from-scratch-in-a-few-days/ https://fosdem.org/2025/schedule/event/fosdem-2025-5148-adve... , last slide.
commiefornia 1y ago
[flagged]
cashsterling 1y ago
I think Ada is a great language and it is completely possible that Ada will experience a resurgence in coming years.. especially as LLM's are used more and more to generate software. ADA/Spark can provide very robust guide rails for correctness (so can Rust) of 'AI' generated code.

110 points by etrez 1y ago

See also part 2: https://gautiersblog.blogspot.com/2025/07/writing-bzip2-encoder-in-ada-from.html https://gautiersblog.blogspot.com/2025/07/writing-bzip2-enco...

rustcleaner 1y ago

Why did Mozilla reinvent the wheel with Rust when we had Ada/SPARK?

Jtsummers 1y ago
SPARK 2012 was what made SPARK viable for a broader audience. Earlier versions of SPARK were not really properly integrated into Ada (SPARK annotations were in comments). SPARK also restricts what is expressible to what is provable within SPARK (which expands over time), this has some important consequences for concurrency and parallelism (using the "concurrency is not parallelism" distinction). So it would have been hard for Graydon Hoare to use SPARK 2012 in 2006 when he started on Rust, and the limitations around concurrency in SPARK 2012 would have been a non-starter for the objectives of Rust as adopted by Mozilla.
steveklabnik 1y ago
Glibly, because they’re not the same language. I don’t think I’ve ever heard Graydon comment on Ada specifically, but early Rust was very different than today’s Rust. Funny enough, I’d argue that early Rust was much closer to Ada than the Rust we ended up with. One thing that makes Ada and current Rust different is that Ada does a lot more checks at runtime than rust does, and is more okay with features that have more of a runtime than Rust is. Another is that Ada doesn’t guarantee memory safety at compile time, or at least, it did not at that time. I believe that with the new Spark features that are inspired by Rust that recently landed may bring parity here, but I haven’t had time to investigate those yet. But really, they're just very different languages from each other. There's no reason they can't coexist.

danbruc 1y ago

For those only having a quick look, the charts do not have the y axis start at zero, the differences are much smaller than it looks.

Sesse__ 1y ago
Also, they seemingly already had a BWT lying around (which is seemingly not counted in “from scratch in a couple of days”), and there is no mention of speed.
- vintermann 1y ago
  He didn't specify that the demo of BWT was in Ada, or his own.
- sltkr 1y ago
  It seems like author means his implementation is competitive in terms of _compression ratio_ only, and this is achieved in the final Huffman encoding step. From that perspective the BWT implementation isn't very interesting because the BWT is deterministic, so the effect on compression ratio doesn't depend on which implementation was used.
etrez 1y ago
The data in question cannot be compressed to zero, or close to zero, by far.

tombert 1y ago

I know the history of why Ada failed, but it always seemed like such a neat language that shouldn't have failed. It seemed like it should have been the standard for a lot of desktop applications for the 90's and 2000's.

steveklabnik 1y ago
I am curious, knowing that history, why do you think that it shouldn't have? I have my own thoughts that I'd be happy to share, but I don't want to spoil your opinion with them. (This goes for basically anyone who's interested in talking about it, I think it's a fascinating bit of history.)
- tombert 1y ago
  I just feel like it emphasized safety in a way that C doesn't, while still being fairly high performance. It always seemed like a neat language.
  - steveklabnik 1y ago
    Gotcha, thanks :) I wouldn't disagree with either of those things at a high level, but I think in practice, the details matter, and it's more of those details that led to the present state than the high level goals, which certainly were laudable.
  - fsckboy 1y ago
    it's not like we didn't know about safety back then, but computers were slow, memory was limited, compilers had to be small, optimization was rare, and C was screamingly fast. At the same time, when major compiler vendors couldn't even get their Ada compilers out the door in project overruns measured in years, Mitch Kapor's 1-2-3 was written and took over the spreadsheet market (dethroning the incumbent Visicalc) and it was written in assembler, not even C, and barely had memory to spare on user machines (memory? there was barely address space left to spare). The tradeoffs were authentic, and there was zero enthusiasm for Ada among programmers or entrepreneurs looking to get products launched. The mainframe world could have been different but the personal computer software market was exploding in a way larger systems never did. (oh and let me add, all the undefined behaviors back then were very clearly defined (perhaps over a small field of options) and extremely useful, and should have been left that way; shoot out a compiler warning or error if they get your panties in a bunch)

whartung 1y ago

Well that was disappointing. I was hoping to see a discussion about writing a zip encoder in Ada. How the language was used, values of the language for this kind of work. How it’s easier or harder to do. Maybe a bunch of Ada source code. Simply as one who does not use Ada I had hoped to be a bit more informed about it.

andsoitis 1y ago
Bottom of page links to the sources: https://github.com/zertovitch/zip-ada https://github.com/zertovitch/zip-ada
etrez 1y ago
Thanks for the feedback. Multiple posts are planned on that topic. For parts 1 and 2 (so far the only ones existing) I preferred explaining the context and the remarkable simplicity of the BZip2 format. In part #4, I will try to show why the customisable types in Ada fit so well compression software. Be patient: writing articles about writing software takes much more time than writing the software itself! In the meantime, there is a short preview of that in recent presentations - notably FOSDEM 2025: https://fosdem.org/2025/schedule/event/fosdem-2025-5148-advent-of-compression-writing-a-working-bzip2-encoder-in-ada-from-scratch-in-a-few-days/ https://fosdem.org/2025/schedule/event/fosdem-2025-5148-adve... , last slide.

commiefornia 1y ago

[flagged]

cashsterling 1y ago

I think Ada is a great language and it is completely possible that Ada will experience a resurgence in coming years.. especially as LLM's are used more and more to generate software. ADA/Spark can provide very robust guide rails for correctness (so can Rust) of 'AI' generated code.