HNHacker News
TopNewBestAskShowJobs

twotwotwo

1,841 karma · joined June 24, 2012

submissionscomments
twotwotwo··on How much faster is making a tar archive without gzip?
When compressing, window size is a tunable option. I think the compression level sets it implicitly, but it can be set explicitly using brotli -w or windowLog in the advanced zstd API (https://facebook.github.io/zstd/zstd_manual.html).

Decompressing many streams at once is more interesting. The decompression APIs do let you specify a max history-window size, but e.g. HTTP won't let you advertise a window size limit, so all you can do is error out if the response would take too much memory to decode. You can just not advertise support for new Content-Encodings at all if it's a concern.

twotwotwo··on How much faster is making a tar archive without gzip?
For anyone who wants to try this, zstd -T0 uses all your threads to compress, and https://github.com/facebook/zstd has a lot more description. Brotli, https://github.com/google/brotli, is another modern format with some good features for high compression levels, which also has Content-Encoding support in web browsers. You might also want to play with compression levels (-1 to -11 or more, zstd's --fast=n); they may not map 1:1 to gzip's.

One reason these modern compressors do better is not any particular mistake made defining DEFLATE in the 90s, but that new algos use a few MB of recently seen data as context instead of 32KB, and do other things that would have been impractical in the 90s but are reasonable with modern hardware. The new algorithms also contain lots of smart ideas and have fine-tuned implementations, but that core difference seems important to note.

twotwotwo··on Hash collisions and exploitations – Instant MD5 collision
One thing that, for me, sort of undermined the idea of adding strength "around" a weak hash was the multicollisions paper: https://www.iacr.org/archive/crypto2004/31520306/multicollis...

Intuitively you might think concatenating two hashes could make something way stronger than either, but the way these functions were constructed, that isn't necessarily true. It also shows a trick to efficiently make exponentially more collisions with linearly more work. It's not that those specific tricks work against every idea for fortification; the paper says it doesn't break some schemes you'd expect it to. But it does show that a weak Merkle-Damgård compression function has weird indirect effects, and that makes things built on one seem shakier.

It can make some difference to try to build a system not to rely on collision resistance if possible, or not to give the attacker full control over the input to the hash. For example, CAs started putting a random serial number not predictable by the requestor into the generated cert, so the attacker couldn't predict all of the content being signed. They still moved off SHA-1, of course.

There are lots of good things to say about newer functions. They do more work (more rounds, bigger state), may make better choices of where to spend their effort (newer functions seem to mix bits faster), and use today's CPU capabilities effectively (recent hashes support SIMD parallelism; SHA-512 uses your 64-bit ALU; SHA-256 even has x64 instructions).

twotwotwo··on J40: Independent, self-contained JPEG XL decoder
I really appreciate the work that must have gone into narrowing down those bugs. There's a reason for the insistence on multiple independent implementations for new standards; the Internet owes you one.
twotwotwo··on Faster zlib/DEFLATE decompression on the Apple M1 (and x86)
> Also super interesting to find out that Deflate was still so suboptimal after all these years.

Optimization can be a moving target!

Many of these changes only help on newer processors, rather than being speedups that would have worked since zlib was written. Some are about using instruction-level parallelism that just wasn't available years back, and a few changes relate to other specific changes in CPUs, like using bigger tables to better exploit bigger caches or using specific new instructions.

You could say something related about gains from more modern compression formats: their design decisions make sense in today's hardware context, where DEFLATE's made sense in the 90s. For example, a 4MB history window is reasonable today but wouldn't have been when RAM was much more expensive and therefore limited. Folks were making smart decisions both then and now!

twotwotwo··on Ask HN: Who is hiring? (July 2022)
Company: ActionKit (a division of NGP VAN)

Company site: https://actionkit.com/

Position(s): Senior software engineer

Location: Fully remote in the United States

Description: ActionKit is used by over 150 progressive groups and not-for-profits to help tens of millions of online supporters contact decision makers, donate money, and take action online and offline. Our clients–the ACLU, MoveOn.org and others–use our tools to protect reproductive rights, fight climate change and more. Our scalable, flexible tools and APIs make us the choice of some of the most tech-savvy progressive organizations using the Internet to fight for good.

We’re a small, tight-knit team where everyone wears a lot of hats. As a software engineer, you’re responsible for the detailed design of your features, not just coding them, and developers often propose feature ideas. All engineers’ work touches various parts of the product, support, and operations. Every engineer, including you, takes a shift of at least a few hours each week answering clients’ support tickets.

A longer description is at https://bit.ly/3NAEw8G – please give it a look!

Tech stack: Python, Django, MySQL. We’ll consider related experience, too!

Compensation: $150-170k depending on qualifications and experience. Generous PTO, parental leave, health insurance, 401(k).

Contact: rfarmer at everyaction dot com or apply at https://bit.ly/3yANApN

There’s no posting for it currently, but we’re also interested in resumes for a site reliability engineer position. Candidates need substantial experience in SRE or operations, and need to be comfortable writing Python, but we’re looking more for skills in systems, cloud, and database administration than application development.

twotwotwo··on When network is faster than browser cache (2020)
Agree with GP that this is getting pretty far off the article, but also--I think remote caches in datacenters are sometimes as much about making the cache shared as about the storage latency.

If you have a lot of boxes running your application, sometimes it's nice to be able to do an expensive thing once per expiry period across the cluster, not once per expiry per app server. Or sometimes you want a cheap simple way to invalidate or write a new value for the full cluster.

The throughput and latency of SSDs does make them a workable cache medium for some uses, with much lower cost/GB than RAM, but that can be independent of the local/remote choice.

twotwotwo··on Guetzli vs. MozJPEG
It exists! https://github.com/google/gipfeli

It was aiming for better compression than LZ4 at much higher speeds than deflate. Now brotli and zstd on their faster settings mostly beat it in that niche.

twotwotwo··on Static B-Trees: A data structure for faster binary search
> I can replay the edits from an 11 page academic paper in 5ms.

That's super cool.

FWIW, what got me curious about RRB trees and so on was the idea of trying for a structure that's fast in some happy cases and degrades to...maybe slow but not, say, quadratic. The thread around https://news.ycombinator.com/item?id=24357976 and got me started and mentions some other fun stuff, including a "tier vector" with sqrt(N) insert/remove anywhere.

twotwotwo··on Static B-Trees: A data structure for faster binary search
Wow, jumprope is really cool!

I'd had, but never gotten at all close to implementing, this idea of something like a a mutable RRB tree (think https://docs.rs/im/latest/im/struct.Vector.html but, again, mutable) with somewhat chunky (say, few-KB) gap buffers as the leaves. The tree gives you asymptotically not-terrible behavior with zillions of items, and the gap buffers could help practical performance when there's a lot of locality in your accesses.

I figure merging two lists of items or filtering some items out of a list might have the sort of locality of edits gap buffers handle well, and largish gap buffers could allow iteration to mostly spend time walking through contiguous chunks.

I still don't know how well something like that applies to a non-rope use case, but it's incredibly cool to see you actually did the work to build a hybrid structure out, validated it, and it does very well.

twotwotwo··on Recovering redacted information from pixelated videos
You should be able to do better than just aligning and averaging frames. (Edit: looks like MauranKilom knows what they're talking about here, and expresses in their comment it clearer than I could.)

Imagine you were running averages on successive windows of a 1D array--when the average changes, that tells you the difference between the values that entered your window and the ones that just left. That's information about a sliver of data much smaller than the overall window. It's weirder with 2D and random-ish movement, but if your average (pixelation) filter is moving across text due to camera wobble or such, when the average goes up and down tells you something about where edges are in the content underneath.

I'm butchering the words because this isn't my thing, but this feels like it might be related to some actual signal-processing task (i.e. undoing some kind of signal-mangling that happens in the wild) which increases the chance that there's some good or at least well-studied solution.

The brute-force-ish approach for text reconstruction would also probably more effective if it checked against a few shifted-around blurred copies of the text, rather than just one.

twotwotwo··on Sequencing your DNA with a USB dongle and open source code
All interesting! Thank you.
twotwotwo··on Sequencing your DNA with a USB dongle and open source code
A researcher mentions using a compact index based on the Burrows-Wheeler Transform to fit things in less memory compared to using a huge hashtable.

I see open-source implementations of BWT-based indexes (FM-Index/FMtree) out there. Out of curiosity, does anyone know of anything using BWTs for compact indexes in more everyday uses (like full-text search), or alternately reasons it doesn't really work outside the genome-alignment use case? Likely it only 'pays for itself' if you really need the space savings (like, it's what makes an index fit in RAM) or else we'd see it in use more places. It'd still be kinda neat to actually see those tradeoffs.

twotwotwo··on Don’t be spooky
Nah, different levels of trust are a thing but it doesn't solve spookiness. People will, rationally, think about the range of possibilities for what you might want to talk about, and if you leave that range as "absolutely anything" it includes bad news.

Right now, it also complicates things that so much communication is over toneless chat or email; something that's clumsily worded or just brief can come across a lot worse than it was meant.

Years back, I was entirely remote my first year at the job. When I finally went to a work retreat I was shocked how nice people were to me. For the whole year I'd thought no one liked me and I was on the verge of being fired! (Also, no one's faces looked how I had guessed from their voices on conference calls :D)

twotwotwo··on How quickly do algorithms improve?
(Once more thing I might put in the list of "not a big-O improvement but a rearrangement that made new things possible" is an essentially economic observation Google and others made: once you're planning to serve enough queries/sec, putting unreasonable-sounding quantities of data into expensive storage (like much of your Web search index in RAM) starts to make sense. I saw it referred to as "online data-intensive" at https://perspectives.mvdirona.com/2012/03/power-management-o... and linked papers but don't know if it has a more common name.)
twotwotwo··on How quickly do algorithms improve?
The statement more directly backed up by the graphs in the paper is "changes in big-O did more to speed up solving large instances of some problems than did increase in SPECint," and they seem to mean really the same problem. The paper is at

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=954...

It loses any feeling of objectivity, but it'd be interesting to broaden the question to approximate or specialized solutions, or things that make larger problems practical to solve without improving big-O. For some examples:

- probabilistic sketches have been very successful at approximately answering questions that took a lot more work to answer exactly

- adapting algorithms to hardware like GPUs doesn't reduce how many operations are done, but can make the operations cheaper/faster for the right problem

- similarly, a good parallel or distributed approach to a problem doesn't change the big-O, but is often what allows scaling up to big n in practice

- the B-tree (1970) did not improve on the big-O of the AVL tree (1962), but it made databases as we know them a lot more practical

- LSM trees and compressed columnar storage also don't improve big-O, but provide big benefits for write-heavy and scan-heavy workloads

Generally that pushes me more towards "hardware isn't responsible for all the advancements". Also, there's a fun conversation (happening out there, I assume) about how to value the sort of work that's more pragmatic than improving on a complexity bound but also more fundamental than just tuning some asm or C.

twotwotwo··on Show HN: Static.wiki – read-only Wikipedia using a 43GB SQLite file
That's super cool.

The autocomplete trickiness is fun. Looks (from links in GitHub) like it's using full-text search and currently needs to scan a lot to rank results. Doing just prefix search might be a cheap half-solution to autocomplete, and maybe layering on hacks around stopwords etc. can get you a bit further.

For another angle, enwiki's full compressed list of titles (enwiki-20210720-all-titles-in-ns0.gz) is 86MB. Grabbing the whole dang thing (in the background?) and doing something with it client-side is a different sort of approach from what this page is going for but not unthinkable.

twotwotwo··on Updating the Go Memory Model
Others said this different ways, but I think the scenarios where you don't get an immediate segfault at the bad read/write are the trickiest ones--hard to debug, at least. One flavor is, say, writing past the end of a slice b/c you read the pointer from one slice and len/capacity from another. If it segfaults, it might be later when the clobbered object is next used.

A few years back someone at Dropbox mentioned tricky prod-only races were a real problem for them sometimes, for instance: https://about.sourcegraph.com/go/go-reliability-and-durabili...

That's where I start dreaming about best-effort detection of races in production binaries or even just reducing the chances of torn reads. Years back there might have been other options, like explicit private vs. shared heaps with more controls on the shared heap, but there seems to be a more restricted set of choices now.

twotwotwo··on Updating the Go Memory Model
Just in theory: pointer/capacity pair is atomic, then you read len non-atomically and check it's less than cap before using it. Slice header today puts len before cap, but, like, if we're dreaming.

You'd probably hit other walls. I'm def. not trying to say it's straightforward!

twotwotwo··on Updating the Go Memory Model
FWIW, I meant race semantics similar to Java's--weird things happen but type/memory safety remains. Not the whole Java runtime model with object headers, etc.

It's obviously, uh, quite an Exercise for the Reader(tm) to figure out the best path to avoid memory unsafety given races in line with other Go priorities (as a starting point, imagine a ton of expensive atomics accessing certain pairs on the heap, downgraded to regular loads/stores if the compiler can prove it's safe). But I was trying to say it seems harder to get there now that certain things are set in stone and regressing perf of anything is going to be bad for some user out there.

twotwotwo··on Updating the Go Memory Model
Java's trick is maintaining memory/type safety in the presence of races. You might crash, and your application might not see the values it expects, but you never get a buffer-overflow-like situation where Java's internal structures might get corrupted in arbitrary ways, for example.
twotwotwo··on Updating the Go Memory Model
> Note that this means that races on multiword data structures can lead to inconsistent values not corresponding to a single write. When the values depend on the consistency of internal (pointer, length) or (pointer, type) pairs, as is the case for interface values, maps, slices, and strings in most Go implementations, such races can in turn lead to arbitrary memory corruption.

That second sentence is one of the painful things about the Go memory model--Go is type and memory safe if you avoid explicitly unsafe things, except for data races on those structures.

I wonder what you can practically do to mitigate that at this point; doesn't seem like you go back and change things to be like Java. Can there be some best-effort detection for races in those specific places that's fast enough to run in prod (like I think they did for maps)? I also recall some Go mailing-list post I can't find suggesting that an SSE 128-bit move, while not guaranteed not to tear, seemed to tear only rarely in their tests on the chips of the time; is that true and is there anything there? I imagine fully preventing the problem with atomic reads/writes of these pairs from the heap is a clear no-go performance-wise, and might involve ABI-changing alignment guarantees.

[Edit: SSE2 behavior is discussed here https://stackoverflow.com/questions/7646018/sse-instructions... which is mentioned in a comment at https://research.swtch.com/gorace which seemed to inspire it. Chance of a race seemed to depend on CPU model at the time, bad on the old Core Duo, better on some server chips another answerer tried. Good on my laptop FWIW!]

Probably hard for anything to happen here because any performance regression is hard to swallow, the race detector is close enough for many, and anything you do won't be a 100% solution anyway. Which is a bummer.

twotwotwo··on The Untold Story of SQLite
> The 100% MCD [modified decision/condition coverage] tests, that’s called TH3. That’s proprietary. I had the idea that we would sell those tests to avionics manufacturers and make money that way. We’ve sold exactly zero copies of that so that didn’t really work out.

That'd be an awesome contribution to open source, particularly at a time that there's a lot of collective awareness of how hard it is to secure C programs.

(There's probably still a business reason to keep it proprietary: it's a reason for people to go to them for changes, at least if they want the final product to be thoroughly tested. Alas, 'cause it would be cool to see.)

It's funny that he references preppers, survivalists, and dependency on society near the end, when talking about writing all of your own software dependencies. A while back someone thinking about it from the other end (i.e. saying we generally should accept some dependencies) said almost exactly the same thing in thread at https://twitter.com/hdevalence/status/1214234305754329088 . I draw no deep insight from this, but fun to see the same analogy from two very different perspectives. (Kind of closing the circle, the "let's be real about dependencies" article linked, https://wiki.alopex.li/LetsBeRealAboutDependencies , mentions in passing "SQLite is basically everywhere (for good reason)".)

twotwotwo··on AMD Quietly Launches Recycled Xbox Series X APU as 4700S Desktop Kit
A related cool-idea-that-won't-happen would be some less-locked-down form of Windows in an XBox. More so than last gen's Jaguar cores, this console gen's CPU cores should be fine for PC use for a while.

It'd probably have to be kind of a VM in a 'game', to avoid revamping the outer OS. They'd probably want to nerf the GPU in Windows to reduce folks' temptation to use it to route around the XBox store (for graphically intense games at least), and maybe price Windows to make up for decreased game revenue per console. Even given all that it might let folks with XBoxes cheaply "get a PC" of sorts, and so come a bit closer to the rest of MS's world.

Probably technical, business, and other issues with that, but again, I did say fun idea that won't happen.

twotwotwo··on JPEG XL
++ to making it easier to use other codecs in place of .gif!
twotwotwo··on JPEG XL
Good point. AV1 and AVIF could improve on how some sites (like Twitter) turn actual GIFs into video now.

Also a plus for saving phone snaps, since the camera often saves a short video these days anyway.

twotwotwo··on JPEG XL
Some notable features of JPEG XL that don't show up in side-by-sides:

1) Progressive decoding. Like the original .jpg, .jxl can give you a low-quality image when a fraction of the file is loaded, then a decent-quality image, then the final image. This can give JPEG XL the edge in perceived load speed even when the full .avif is smaller than the full .jxl. (Old demo from a JXL contributor at https://www.youtube.com/watch?v=UphN1_7nP8U )

2) Fast conversion: JPEG XL encoding/decoding is fast without dedicated hardware. Facebook found encode/decode speed and progressive decoding to be points in favor of JPEG XL for their use: https://bugzilla.mozilla.org/show_bug.cgi?id=1539075#c18

3) .jpg repacking: JPEG XL can pack a JPEG1 about 20% smaller without any additional loss; the original .jpg file can be recovered bit-for-bit.

4) Lossless mode. JXL's lossless mode is the successor to FLIF/FUIF, is really good, and also has progressive decoding. AVIF has a lossless mode too, but JPEG XL seems ahead here.

(I know the parent comment is from a JXL contributor, I'm saying this for other folks.)

I think those will give JPEG XL a niche on the Web. Meanwhile I suspect e.g. Android phone cameras will save .avif someday, like iPhones save .heic now. Phones want the encode hardware anyway for video, and you can crunch a zillion megapixels down to a smaller file with AVIF before attention-grabbing artifacts crop up--at low bitrates AVIF seems good at preserving sharp lines and mostly blurring low-contrast details (compare Tiny images).

Finally, worth noting the codecs are different due to a bunch of rational choices by their devs. AVIF is the format for AV1 video keyframes. Progressive decoding doesn't help there, and doesn't jibe well with spatial prediction, which helps AV1 and other video codecs preserve sharp lines. And video codecs need hardware support to thrive anyway, so optimizing for fast software encoding probably wasn't an early priority. Otherwise the new formats have a lot of overlap in fundamentals--variable size and shape DCTs, better entropy encoding, chroma-from-luma, anti-ringing postfilters, etc.

Glad to see support for both getting more widespread.

twotwotwo··on Unreliability at Scale
The "petabyte for a century" problem statement he mentions near the top is fun: can you preserve 1 PB with better-than-even odds of all the bits coming back right in a century? He wrote something about how he saw the durability situation in 2010: https://queue.acm.org/detail.cfm?id=1866298 . He seems to define the problem to allow for maintenance, e.g. check-and-repair operations are discussed.

Broadening a little, I read it as "if you're trying to be more cautious than you usually want for commercial/academic online storage or even backup, what do you do? And would it work?"

A lot (but not all) of the author's Queue piece talks about stats from online storage, which doesn't have some wins you can get if you're entirely about long-term durability.

In online systems, heavy ECC seems out of favor compared to replication for performance reasons, but additional LDPC or RS at the app layer can absorb a substantial % of your volumes having problems, or a ton of random bad blocks. (In a more near-line context, Backblaze uses RS: https://www.backblaze.com/blog/vault-cloud-storage-architect... ) Same for tape -- offline LTO is slow and drives are costly, but the cost/TB and the rated lifespan seem like advantages over HDDs for this specific goal, at least in a narrow engineering sense.

A pile of cryptographic hashes that fits on one device can help you check for and localize errors without sending everything over a network/doing the full ECC dance. If the hash being broken and data tampered with is in your threat model (hey, weird things can happen in a century), you can also hash with a secret nonce you keep separate.

Initially loading a PB with a good chance of no mistakes is a thing too, and durability measures don't totally address that. Maybe your multi-site strategy loads up the original on different hardware at different locations with independent software implementations, and you compare those hashes after you do it.

With all that the hundred-years part is still deeply tricky in a couple ways.

"Lasting a hundred years" is just technologically different from "very low error rate at 5 years." Widely used media like LTO tape seem to max out at a 30y rating, and exotic archive media like the "hardened film" at GitHub's code vault has the big disadvantage of no ecosystem to read it. So seems like you really want refreshes of some sort at intervals, and being sure a task will be done decades from now is hard (assuming high-tech civilization is around and all that--some things just have to be outside the scope of the problem for it to be meaningful).

From that angle, maybe having an online copy of the data is a better investment than the pure engineering perspective would suggest: if other folks can grab a copy of the archive it has a better chance of outliving your organization.

Two, a lot of unknown unknowns crop up at that timescale. A couple decades back we didn't have the experience at scale we do now, and CEEs and other causes of SDC were less on anyone's radar. We could discover something else significant after it's too late to fix. The world can also change in ways that disrupt the durability picture substantially (changing laws or disaster risks, say), short of the types of change that make the whole problem meaningless.

Anyway, fun question, and if you find it fun too, you might like https://www.youtube.com/watch?v=eNliOm9NtCM , a talk on backups from someone at Google that talks about the tape restore after the big GMail glitch and various dimensions of resilience. And I'm sure there are storage papers and Long Now-ish stuff I'm not plugged into about things like this, wouldn't mind hearing about it.

twotwotwo··on NVMe is not a hard disk
> > RAID or storage replication in distributed storage <..> is not only useless, but actively undesirable

> I guess I'm different from most people, good news!

The earlier part of the sentence helps explain the difference: "That is, because most database-like applications do their redundancy themselves, at the application level..."

Running one box I'd want RAID on it for sure. Work already runs a DB cluster because the app needs to stay up when an entire box goes away. Once you have 3+ hot copies of the data and a failover setup, RAID within each box on top of that can be extravagant. (If you do want greater reliability, it might be through more replicas, etc. instead of RAID.)

There is a bit of universalization in how the blog post phrases it. As applied to databases, though, I get where they're coming from.

twotwotwo··on AMD 3D Stacks SRAM Bumplessly
The BIOS on an AMD reference platform refers to there being 1, 2, or 4 "X3D stacks", suggesting that eventually you might be talking about more cache than this: https://twitter.com/aschilling/status/1399701274489151489

(Who knows when/if they get 2/4-high working and at what price: the I/O die needs to be able to track tags proportionate to the total cache size, the compute chiplet needs to support it, and packaging/power/everything else needs to work out. Switch in BIOS doesn't mean the rest is there.)

Other clever thing about this for them is they can keep focusing on one base compute chiplet but turn it into a wider range of SKUs, on top of how they already do that with core count etc. Same chiplet can end up in a product with 32 or 96MB L3/CCD as soon as the first two-high stack comes out and, obviously, more if/when they get 2/4-high going.

← PreviousPage 5 of 19Next →