Bzip3: A spiritual successor to BZip2 • Hacker News Board

Re: Bzip3: A spiritual successor to BZip2

#161

Post by maginx » Sun, Feb 02, 2025, 6:00 PM UTC

jltsiren wrote: post #120

bawolff wrote: post #113

Earlier quoted context omitted.

Magical things are usually built up from the trivial examples. Graph colouring is usually used as a teaching example for zkp, because of how easy it is to understand. Its still amazing how you can go from that example to "Here is a file that anyone can verify (non-interactively) which shows i have a passport and that passport is not from a country sanctioned by the usa but otherwise does not reveal anything about me"…

Things that look magical often stop being magical when you have the right perspective and the right abstractions. The step from a toy example to proving any verifiable statement is just NP-completeness. Which is simple enough that undergraduates are often expected to understand it. Interactive zero-knowledge proofs are also technically non-interactive. They are defined in terms of the verifier evaluating a transcript…

Agreed - I've worked with PKI in many years, and know why the various systems work...in terms of "why you can decrypt again", not in terms of why it is secure (no other way to decrypt) which no one really knows. But if we assume for a moment the systems are secure, it is truly fascinating when thinking about it in abstract terms: Who would have thought, it is possible to give someone an exact recipe to follow that scramble a message to be sent... we can consider e.g. an encryption routine where the public key is inline so it is really just a standalone scrambling problem. Even though it is completely public, it can only be used to scramble and not unscramble. The sender who literally went through the steps to scramble the message, cannot undo what they just did. (the sender could have saved the original before scrambling!). And it is not because data is thrown away it can't be unscrambled - all the information is there there, fully recoverable, but only by the person who made the scrambling-recipe and there's no practical way to deduce this unscrambling recipe from the scrambling recipe.

Re: Bzip3: A spiritual successor to BZip2

#162

Post by altairprime » Sun, Feb 02, 2025, 6:13 PM UTC

klodolph wrote: post #126

altairprime wrote: post #51

Earlier quoted context omitted.

Can BWT be combined with zstd, which uses asymmetric numeral systems?

I think you would just need ANS, not the rest of zstd.

I don’t know enough to evaluate that, but it sounds plausible. Apparently modifying or integrating zstd into custom solutions was a common path in submissions to, at the very least, the GDCC 2021 T2 contest. This is all well outside of my learned competence so I’m just here to learn and ask naive questions.

Re: Bzip3: A spiritual successor to BZip2

#163

Post by toast0 » Sun, Feb 02, 2025, 6:41 PM UTC

jltsiren wrote: post #104

bawolff wrote: post #70

Earlier quoted context omitted.

Yeah. BWT and zero knowledge proofs are my goto examples of CS things that seem like pure magic.

Public-key cryptography is magic. Zero-knowledge proofs are a consequence that's difficult to find on your own but easy to understand once you've seen it. I remember seeing someone (probably Avi Wigderson) demonstrating a zero-knowledge proof for graph coloring on an overhead projector when I was starting my second year studying CS. He had a slide with a graph, multiple slides with different permutations of the same…

> Public-key cryptography is magic.

Public key cryptography is kind of magic, but the basic piece that makes everything work isn't too hard. It's been a while since I took discrete math, so this is a bit rusty, but it should get you in the right direction. It's modular multiplication in a field. If you take a small field and make a times table, you can see the magic. All of the factors that are relatively prime to the modulus will have a pattern that you F times X is only equal to F times Y if X and Y are equal. There will also be a multiplicative inverse so that F times X time I equals X for all X; because of commutation I times X times F also equals X. When you've determined an F and an I, you give your correspondent F and keep I --- then if you multiply your message by F, they multiply it by I and get back the message. If they want to send you a message, they multiply it by I and send it, then you multiply it by F.

There's some other stuff, but that's the magic part, IMHO. You just have to use a bigger field and some other stuff I forgot. ;)

Re: Bzip3: A spiritual successor to BZip2

#164

Post by t43562 » Sun, Feb 02, 2025, 6:56 PM UTC

loeg wrote: post #22

jgalt212 wrote: post #18

I poke around in this space periodically, but I've never found a compelling reason to move away from gzip.

zstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.

> bzip2 -9 -k all.tar 981.78s user 9.77s system 95% cpu 8M memory 17:16.64 total

> bzip3 -e -b 256 -j 12 all.tar 2713.81s user 16.28s system 634% cpu 18301M memory 7:10.10 total

The memory usage is one reason: 8M vs 18301M

Re: Bzip3: A spiritual successor to BZip2

#165

Post by t43562 » Sun, Feb 02, 2025, 7:01 PM UTC

  > bzip2 -9 -k all.tar  981.78s user 9.77s system 95% cpu 8M memory 17:16.64 total
  > bzip3 -e -b 256 -j 12 all.tar  2713.81s user 16.28s system 634% cpu 18301M memory 7:10.10 total

The difference in memory usage might be worth noting: 8M v 18301M

Re: Bzip3: A spiritual successor to BZip2

#166

Post by toast0 » Sun, Feb 02, 2025, 7:11 PM UTC

loeg wrote: post #33

chefandy wrote: post #30

Earlier quoted context omitted.

Yeah I'm sick of this. Did you know you can't even use ext2/3/4 together on the same partition? What a mess.

The ext4/3 filesystems, notably, can read/write ext2 (and for ext4: ext3) filesystems in a compatible way.

IIRC, ext3 filesystems, if properly unmounted can be mounted with an ext2 driver

Re: Bzip3: A spiritual successor to BZip2

#167

Post by Groxx » Sun, Feb 02, 2025, 7:18 PM UTC

t43562 wrote: post #165

> bzip2 -9 -k all.tar 981.78s user 9.77s system 95% cpu 8M memory 17:16.64 total > bzip3 -e -b 256 -j 12 all.tar 2713.81s user 16.28s system 634% cpu 18301M memory 7:10.10 total The difference in memory usage might be worth noting: 8M v 18301M

Probably worth noting that bzip2 also did by far the worst in this. ~7x larger files than the best bzip3. Large memory use is generally required for good compression.

I'm curious how well gzip would have handled this though, as it's generally low memory too, and all the others in that list have FAR more than 8M memory used.

Re: Bzip3: A spiritual successor to BZip2

#168

Post by t43562 » Sun, Feb 02, 2025, 7:29 PM UTC

Groxx wrote: post #167

t43562 wrote: post #165

> bzip2 -9 -k all.tar 981.78s user 9.77s system 95% cpu 8M memory 17:16.64 total > bzip3 -e -b 256 -j 12 all.tar 2713.81s user 16.28s system 634% cpu 18301M memory 7:10.10 total The difference in memory usage might be worth noting: 8M v 18301M

Probably worth noting that bzip2 also did by far the worst in this. ~7x larger files than the best bzip3. Large memory use is generally required for good compression. I'm curious how well gzip would have handled this though, as it's generally low memory too, and all the others in that list have FAR more than 8M memory used.

I think gzip was 5M. This all depends where you are using it e.g. on a Raspberry Pico I'd be using gzip no matter the extra bytes probably.

Re: Bzip3: A spiritual successor to BZip2

#169

Post by yencabulator » Sun, Feb 02, 2025, 8:02 PM UTC

zimpenfish wrote: post #35

linsomniac wrote: post #2

Highlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels

Did a test on a 1.3G text file (output of `find -f -printf ...`); Macbook Pro M3 Max 64GB. All timings are "real" seconds from bash's builtin `time`. files.txt 1439563776 bzip2 -9 -k 1026805779 71.3% c=67 d=53 zstd --long -19 1002759868 69.7% c=357 d=9 xz -T16 -9 -k 993376236 69.0% c=93 d=9 zstd -T12 -16 989246823 68.7% c=14 d=9 bzip3 -b 256 975153650 67.7% c=174 d=187 bzip3 -b 256 -j12 975153650 67.7% c=46 d=189 bzi…

That d=9 sure wins the day there, for me.

Re: Bzip3: A spiritual successor to BZip2

#170

Post by lazide » Sun, Feb 02, 2025, 8:23 PM UTC

skrebbel wrote: post #157

loeg wrote: post #22

Earlier quoted context omitted.

zstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.

> There is no reason to use gzip these days other than backwards compatibility And forward compatibility. The Lindy effect says gzip is likelier to be widely available across platforms and tools in the long term than zstd.

Zip beats all on that front.