danking00

Wow! At first, I expected this to be a demonstration of an AI playing rocket league, but I rapidly realized this is actually a model simulating rocket league. Wild! It feels just like the real game.

danking00

12 months agodiscuss

Feather appears to just be block compressed Arrow IPC [1]. Lightweight compression techniques generally achieve two orders of magnitude faster random access compared to block compression. That’s one of the benefits of formats like FastLanes, Vortex, DuckDB native, etc. DuckDB has a good blog post about it here: https://duckdb.org/2022/10/28/lightweight-compression.html

[1]: https://arrow.apache.org/docs/python/feather.html

danking00

last yeardiscuss

cppreference says [1]:

    A prvalue of floating-point type can be converted to a prvalue of any integer type. The
    fractional part is truncated, that is, the fractional part is discarded.

    - If the truncated value cannot fit into the destination type, the behavior is undefined (even
      when the destination type is unsigned, modulo arithmetic does not apply).

Ugh. Like, surely the C++ stdlib could provide a "give me the best int approximation" function without triggering nasal demons. Sometimes I feel like C++ is not just difficult to use but actively trying to harm me.

[1] https://en.cppreference.com/w/cpp/language/implicit_conversi...

danking00

last yeardiscuss

I think one of my favorite examples of avoiding decompression for great profit (really: health) is PLINK. If you’re not aware, it’s a tool for doing statistical genetics (things like quality control but also inferring population structure, computing relatedness between individuals, and fitting linear models). The code is mind bending to read but it’s blazing fast thanks to “compressing” genotypes into two bits (homozygous reference, heterozygous, homozygous alternate, N/A) and implementing all its operations on this 2-bit representation.

It’s exciting to see more work on compressed arrays make it out into the world. It would have been nice if a lot of PLINK’s bitfiddling functionality was in an accessible native library rather than wrapped up with the rest of that tool.

https://www.cog-genomics.org/plink/2.0/

danking00

2 years agodiscuss

We’ll post a blog post soon with specific, benchmarked numbers, but, in this case, you can have your cake and eat it too!

The compression and decompression throughputs of Vortex (and other lightweight compression schemes) are similar or better than Parquet for many common datasets. Unlike Zstd or Blosc, the lightweight encodings are, generally, both computationally simple and SIMD friendly. We’re seeing multiple gibibytes per second on an M2 MacBook Pro on various datasets in the PBI benchmark [1].

The key insight is that most data we all work with has common patterns that don’t require sophisticated, heavyweight compression algorithm. Let’s take advantage of that fact to free up more cycles for compute kernels!

[1] https://github.com/cwida/public_bi_benchmark

danking00

2 years agodiscuss

Thanks for introducing me to these other formats! I hadn't heard of them yet. All three of fst, JDF, and Vortex appear share the goal of high throughput (de)serialization of tabular data and random access to the data. However, it is not clear to me how JDF and fst permit random access on compressed data because both appear to use block compression (respectively Blosc and LZ4 or Zstd). While both Blosc and Zstd are extremely fast, accessing a single value of a single row necessarily requires decompressing a whole block of data. Instead of O(1) random access you get O(N_ROWS_PER_BLOCK) random access.

In Vortex, we've specifically invested in high throughput compression techniques that admit O(1) random access. These kinds of techniques are also sometimes called "lightweight compression". The DuckDB folks have a good writeup [1] on the common ones.

[1] https://duckdb.org/2022/10/28/lightweight-compression.html

danking00

2 years agodiscuss

Yeah we should be more clear in our description about how our footers differ from Parquet. Parquet is a bit more prescriptive; for example, it requires row groups which are not required by Vortex. If you have a column with huge values and another column of 8 bit ints, they can be paged separately, if you like.

danking00

2 years agodiscuss

Yeah, you and us are on the same page (heh). We don’t want the format to require row grouping. The file format has a layout schema written in a footer. A row group style layout is supported but not required. Specification of the layout will probably evolve, but currently the in-memory structure becomes the on-disk structure. So, if you have a ChunkedArray of StructArray of ChunkedArray you’ll get row groups and pages within them. If you had a StructArray of ChunkedArray you’ll just get per-column pages.

I’m working on the Python API now. I think we probably want the user to specify, on write, whether they want row groups or not and then we can enforce that as we write.

danking00

2 years agodiscuss

See also one of the author's twitter threads: https://x.com/cureffi/status/1806404950055862547

danking00

2 years agodiscuss

Unless I’m misreading, the first two references support the idea that vacancy rates are too low but don’t comment on why.

The last reference indeed argues in favor of too much financialization of housing units but that blog is also tripping a lot of my crackpot alarms.

Can you succinctly explain why you believe the low vacancy rates in major metros (which I think we agree is the cause of high rents / purchase costs) are caused primarily by units which are intentionally held empty despite demand?

In partial defense of your assertion, the FRED data does show that 1/4 to 1/3 of vacant units are for sale or rent at any given time.

https://fred.stlouisfed.org/graph/?g=1oeIe

Total vacancy rate seems to hover around 10%? Rentable and buyable unit rates are an order of magnitude lower.

I’m not convinced that the Fed owning a bunch of mortgages is evidence that private companies bought homes and aren’t renting them. Wasn’t that a bail out to prevent people from losing their homes (because the companies owning the homes weren’t solvent and I guess if the company fails maybe you get foreclosed? I’m not sure why we did things the way we did in 08)

Could not the explanation also be that a lot of homes are in places that lack demand and therefore the owners don’t bother putting them up for sale or rent?

https://fred.stlouisfed.org/graph/?g=1oeII

danking00

2 years agodiscuss

Thanks for the reply and clarification! That’s an impressive throughput. Am I interpreting the behavior correctly to think that: your code has one branch per int and that branch will be predicted well when your integers are all of similar magnitude?

I never fully groked the Zipf distribution but am I correct to conclude the worst case for vu128 would be alternating integers on either side of the branch condition?

Thanks for the link to the slides, also clever!

danking00

2 years agodiscuss

If I’m following, this presents an alternative format and implementation to LEB128 which encodes and decodes substantially faster. Notably, the implementation is quite simple. Cool! And agreed that modern CPUs really suffer from branches.

Should I interpret the plot to mean the average elapsed wall clock time per integer decoded/encoded? And can I conclude the throughput is the reciprocal? So about 100,000 integers per second or around a 1 MB/s of decompressed data.

I know this is a bit unfair because the implementation is much more complex, but my first thought is why I would use vu128 instead of Lemire’s Stream VByte: https://arxiv.org/abs/1709.08990

A slight tangent but I stumbled on this library which stores floats XOR’ed with the previous float in the stream: https://github.com/velvia/compressed-vec it seems really clever to me! They reference “Gorilla: A Fast, Scalable, In-Memory Time Series Database” which in turn references two 2006 papers: “Fast Lossless Compression of Scientific Floating-Point Data” and “Fast and Efficient Compression of Floating-Point Data”. Frustratingly, the FB paper doesn’t benchmark their XOR-based floating point encoding but the earlier two papers do.

danking00

2 years agodiscuss

I think it might help readers to include a narrative about an example application. Perhaps I’m in the minority but I tend to think of Bloom filters as a way to reliably know something isn’t in a set (e.g. so as to not run an expensive disk read). This data structure seems to view them the dual way: “this is maybe the right value for this key”.

I’ve seen that view work for visualizations like approximate CDFs and medians where I have some statement like “with probability p, the value differs from truth by less than e”. Is this data structure used in a similar way? My instinct is that visualizations having a low rate of being wrong is OK because the human will follow up that visualization with more tests. In the end you have lots of evidence supporting the conclusion.

danking00

2 years agodiscuss

There’s also a lighter weight Nature News article about it https://www.nature.com/articles/d41586-024-01449-y

danking00

2 years agodiscuss

I was surprised by the last clause in your last sentence, but you’re absolutely right. https://www2.census.gov/geo/docs/reference/ua/ua_list_all.tx...

LA edges out NYC: 7000 to 5300. Presumably in individuals per square mile.

danking00

2 years agodiscuss

I gathered a table for Google and Amazon's options. I do not have experience with on-prem solutions so I don't know how to compare these prices to the cost of owning and operating hardware. I'm sure its cheaper over time for the hardware but I imagine you need sufficient scale to amortize the personnel costs.

Storage

    | product              | price (USD/GiB-month) | price (USD/IOPS-month)            | claimed max read bandwidth (MiB/s) | minimum price to achieve bandwidth |
    |----------------------|-----------------------|-----------------------------------|------------------------------------|------------------------------------|
    | GCP NVMe Local SSD   | 0.1046 [1]            | 0.00                              | 12,480 [2]                         | 13,000 USD/month [3]               |
    | AWS io2 SSD          | 0.1250 [4]            | 0.065 [4,5]                       | 4,000 [6]                          | 1,042 USD/month [4,6,14]           |
    | AWS io1 SSD          | 0.1250 [4]            | 0.065 [4,5]                       | 500 [7]                            | 135 USD/month [4,7,15]             |
    | Google Cloud Storage | 0.0200 [8]            | 0.0004 per "1k Class B Op" [8,16] | 23,842 [9]                         | [10]                               |
    | AWS S3               | 0.0230 [11]           | 0.0004 per 1k GET [8,16]          | 11,921? [12]                       | [13]                               |

You could build a similar table for compute but it gets complicated. FLOP seems like a reasonable unit of compute, but there are things other than FLOPs (e.g. decoding your column-oriented compression scheme).

I've tried to do this comparison a few times but I usually find it hard to get clear aggregate FLOP numbers for GPUs. GPUs also require caretaker CPUs and I don't have experience using them so I'm not certain how to spec a VM that can practically saturate the compute of the GPUs. My gut instinct is that the big compute consumers must be able to arbitrage this to some extent by shifting some workloads to chase the cheapest FLOP.

EDIT(2x): Table formatting. We could really use some Markdown styling on HN.

EDIT3: Clarify incomparability of IOPS and GETs.

[1] https://cloud.google.com/compute/disks-image-pricing#localss...

[2] https://cloud.google.com/compute/docs/disks/local-ssd#nvme_l...

[3] For 12TiB. https://cloud.google.com/compute/docs/disks/local-ssd#nvme_l...

[4] https://aws.amazon.com/ebs/pricing/

[5] We only need need 16,000 IOPS for peak performance of io2, so I ignore the drop in price at higher volumes.

[6] https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/provisio...

[7] https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/provisio...

[8] https://cloud.google.com/storage/pricing#price-tables

[9] https://cloud.google.com/storage/quotas#bandwidth

[10] Honestly not sure. You can do 5,000 parallel "reads" per second to a single object. I'm not sure what kind of instance you need to receive 23,842 MiB/s or if a single object can actually deliver that much bandwidth. https://cloud.google.com/storage/quotas#objects

[11] It gets slightly cheaper as volume goes up. https://aws.amazon.com/s3/pricing/

[12] I could not find a clear answer, but it seems at least 100 Gbps (11,921 MiB/s) https://repost.aws/knowledge-center/s3-maximum-transfer-spee...

[13] As with Google [10], I'm not really sure.

[14] For 16GiB and 16k IOPS.

[15] For 40GiB and 2000 IOPS.

[16] Not really comparable to provisioned IOPS because you pay for the IOPS once per month whereas you pay for every individual GET request.

danking00

2 years agodiscuss

It'd be interesting to see a peak-sequential-bandwidth by cost-per-gigabyte plot. The number I keep in my head is 500 MiB/s, but you're right that there are much faster drives out there [1]. Of the public clouds: Google's "Local SSD" claims ~12,000 MiB/s but they're ephemeral and you need 12 TiB of disks to hit that bandwidth [2][4]. AWS has these io2 SSDs which claim 4,000 MiB/s [3].

On the other points of the article, even if you had a huge disk array plugged into the machine, how many cores can you also plug into that computer? I suppose there will always be a (healthy, productive) race here between the vertical scaling of GPUs + NVMe SSDs and the horizontal scaling of CPUs and blob storage.

EDIT: formatting.

[1] First Google result is Tom's hardware: https://www.tomshardware.com/features/ssd-benchmarks-hierarc...

[2] https://cloud.google.com/compute/docs/disks/local-ssd#nvme_l...

[3] https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/provisio...

[4] The ephemerality has two downsides. First, you have to get the data onto that local SSD from some other, probably slower, storage system (I haven't benchmarked GCS lately, but that's probably your best bet for quickly downloading a bunch of data?). Second, you need to use non-spot instances which are 3-6x the price.

danking00

2 years agodiscuss

Most effective learning experience I ever had was reading the relevant book chapter before class, taking some broad notes to structure my understanding, and then asking questions during class when either the lecture didn’t make sense or we reached a confusion I had from reading.

I only managed one class like that and only near the end of my undergraduate career. Both earlier in ugrad and in grad school I was way too busy barely staying afloat to be so meticulous about my education.

danking00

3 years agodiscuss

Thanks for all your comments thus far! I have an axe to grind with the US immigration system but it’s best to grind it on a stone of facts.

Yeah, I was a bit loose with the parents situation. I made a general comment based on a specific circumstances. That’s my bad.

To petition for parents you need to be a full citizen not simply a green card holder. That adds five years. For India-born folks, this practically puts their parents date over a decade away. Meanwhile those parents become elderly and live thousands of miles from their grand children. So, for a lot of folks who spent years pursuing PhDs and have Indian passports their parents might immigrate at ~seventy while they’re in their fifties. I dunno man, that’s fairly old. Their parents might not make it.

I can’t edit the original post anymore, so your comment will have to serve as the correction.

danking00

3 years agodiscuss

For India alone, Wikipedia says ~8% or ~100 million have a BS. I was more focused on PR/citizenship in my post. I do not know what qualifies you for an H1-B.

In the second point, I only have an imprecise opinion which is that I’d rather suffer some loss of quality of life personally if the median human experience is raised.

Would you support kicking out someone who doesn’t qualify for an EB or H1-B (in practice, you’re kicking out non degree holders) for a foreign born person who does qualify? If not, it seems to me we are embracing a lottery of birth place. To be clear, I’d like to see substantially more freedom of movement even if it means reducing my quality of life.

Submissions

Brainwide silencing of prion protein by AAV-mediated [..] epigenetic editor

Long somatic DNA-repeat expansion drives neurodegeneration in Huntington disease

comments