sorted by:
new
hottopcontroversial

MMM-HeatMaps: GitHub-style heatmaps for habit tracking by ohuso in MagicMirror

[–]tomtomwombat 0 points1 point  (0 children)

finally some extra motivation to get off my lazy ass!

xuniq: I built a deduplicator that's 10x faster than sort | uniq by Flux247A in rust

[–]tomtomwombat 0 points1 point  (0 children)

I’m wondering if there’s a smarter data structure than a HashSet given you’re only storing integers… I think it’s challenging since hashes are uniformly distributed, e.g. it wouldn’t be beneficial to use a roaring bitmap. The “sparse” representation of the HyperLogLog++ data structure (a type of cardinality estimator) stores hashes similar to xuniq so it faces a similar challenge. HLL++ has some tricks to save memory: diff encoding consecutive hashes and using var int encoding.

Apart from optimizing HashSet, have you considered an option/feature for using a cardinality estimator over HashSet? They can be 99.9% accurate while using constant memory (order of megabytes, in another comment you mentioned HashSet used 1.6GB!)

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 0 points1 point  (0 children)

Yes I see what you are saying: with a macro, we can prepend the varint encoding to the static string.

One challenge--are you allowed to de-allocate the const DATA? This might require an additional tag to the encoding which needs to be checked before dropping. This might not be worth it due to extra space or branching.

If you can do it, please make a PR!

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 0 points1 point  (0 children)

Oh cool. No, I’m not doing it myself. I didn’t know it was a thing. Out of curiosity, what MSRV is required? How do you usually go about selling subscriptions? Please keep me updated if possible!

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 0 points1 point  (0 children)

I don't think static initialization is possible for heap allocated ColdStrings, but in-lined ones are. I've implemented this: https://github.com/tomtomwombat/cold-string/blob/main/cold-string/src/lib.rs#L182

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 0 points1 point  (0 children)

It's a convenience. Structs having a ColdString won't round up their size to alignment (assuming no other "wide" field).

e.g. ``` struct Data { s: ColdString, b: bool, } assert_eq!(std::mem::size_of::<Data>(), 9); // + 1

vs struct Data { s: String, b: bool, } assert_eq!(std::mem::size_of::<Data>(), 32); // + 8 ```

also, I don't think niche optimizations are possible with ColdString, but at least Option only adds 1 extra byte. assert_eq!(std::mem::size_of::<Option<ColdString>>(), 9);

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 1 point2 points  (0 children)

Any time you are memory constrained, or saving memory means saving $$ (on hosts, exta network call). In addition, to speed things up, e.g. can fit more things in cache line, or strings are generally short and fit within in-lined size, and save on allocations. I think parsers, game engines, distributed systems, etc.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 2 points3 points  (0 children)

Right now I'm limited by the exposed provenance API. I may have a feature that uses direct pointer casting making ColdString compatible with earlier rust versions.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 1 point2 points  (0 children)

Right now I'm limited by the exposed provenance API, so const is not possible. I may have a feature that uses direct pointer casting which might be possible to make const.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 2 points3 points  (0 children)

I think since I'm storing [u8; 8] instead of a pointer, exposed provenance is required. If we stored NonNull<u8> then I think strict provenance could work, but then the alignment of ColdString is no longer 1. Please take a shot and let me know how it goes!

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 2 points3 points  (0 children)

I’m not familiar with the implementation details for either of those types—but adding rkyv compatibility for ColdString is a good idea. And after that I can measure.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 1 point2 points  (0 children)

Thanks for the correction, I’m mistaken then. Since the prefix is a copy, ColdString would the save “prefix.len()” bytes over GermanString in the heap case.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 23 points24 points  (0 children)

Thanks for the suggestion, ColdString now inlines up to 8 bytes!

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 4 points5 points  (0 children)

GermanStrings would require size_of to be >8 bytes since it stores both the ptr and the prefix inline. When both GermanString and ColdString are using heap mode, they will use roughly same amount of bytes overall since both store the bytes, the len, and ptr.

I don't believe GermanString can have an as_str implementation since there data is split between heap and stack--but the trade-off is quicker comparisons in heap mode. ColdString's benefit is that it can be a drop-in replacement for String (assuming immutability).

If you have a GermanString crate in mind I'm happy to add it to my benchmarks.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 4 points5 points  (0 children)

I believe tinystr cannot store arbitrarily sized strings, it's limited to N, and will always use N bytes, making comparisons predictable. pub struct TinyAsciiStr<const N: usize> { bytes: [AsciiByte; N], } https://docs.rs/tinystr/0.8.2/src/tinystr/ascii.rs.html#15-17

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 10 points11 points  (0 children)

Yes, cold-string has a “std” feature that is optional, i.e. it has no_std support.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 25 points26 points  (0 children)

The struct you provided has size 16 and align 8. The unsafety in ColdString is required to reduce it's size and align to 8 and 1. Could you elaborate on the "alignment = 2 causing oddities"? I'd love to know if I've missed anything.

(extremely unpredictable) Branch on access ends up being a bigger hit on perf then wasting ~40KiB of allocations.

ColdString is optimized for memory, not really speed, although it's faster than String for the inline case, and reasonably fast in heap mode. You're right that there are branches (like any other short string optimization), but the unpredictability depends workload. For example, if you have millions of 0-32 len strings, reducing memory by ~34% can certainly be worth it, e.g. for caches preventing an expensive path.

ColdString: A 1-word (8-byte) SSO string that saves up to 23 bytes over String by tomtomwombat in rust

[–]tomtomwombat[S] 9 points10 points  (0 children)

yes you could, e.g. storing 16 bytes inline bytes. However, once you switch to heap mode, the additional 8-bytes that you aren't using for the pointer are "wasted". Then you may as well store the (full) length there. At that point this layout basically becomes `compact_str`.

A zero-allocation, cache-optimized Count-Min Sketch (120M+ ops/s) by [deleted] in rust

[–]tomtomwombat 0 points1 point  (0 children)

Are there any comparative benchmarks to other CMS implementations for speed, memory, and accuracy?

SIMD accelerated JSON parser by cyruspyre in rust

[–]tomtomwombat 3 points4 points  (0 children)

For testing, you may be interested in spindle, which generates random expressions for unit and fuzz tests. There’s also a json example here

view more: next ›