trentnelson

10 ms·

61.
by trentnelson 6y ago
> NumPy core developer Sebastian Berg chimed in as well. He suggested that it could take up to a solid year of work to support subinterpreters in NumPy. Whoa, that's a shame. I actually found it really easy to patch NumPy to make i
62.
by trentnelson 7y ago
Do you have the source data available? Or can you make an anonymou version available?
63.
by trentnelson 7y ago
Got any similar recommendations for college-level probability/stats stuff?
64.
by trentnelson 7y ago
Just wanted to say I really like and appreciate this, great work!
65.
by trentnelson 7y ago
You might find this deck interesting: https://speakerdeck.com/trent/pyparallel-how-we-removed-the-... There is no equivalent in UNIX land to the thread-agnostic asynchronous I/O primitives available on NT. When p
66.
by trentnelson 7y ago
> DEC cancelled it. Cutler and his team left and went to Microsoft. MS didn't know what to do with this élite group so it gave them OS/2 3 to finish. Based on the Showstoppers book -- it's more like: Bill Gates knew the d
67.
by trentnelson 8y ago
> Traps don't quite work the way you'd want in C [1]; there's no way to catch a trap that occurs in a specific region of code. Ah, unless you're in NT land, which makes lexical scoping of traps very easy: https:&#x2F
68.
by trentnelson 8y ago
> uses of pointer indirection that look like the student kept adding or removing asterisks until it didn’t crash Oh c'mon, that's practically a right of passage when learning C or C++ for the first time, especially if you'
69.
by trentnelson 8y ago
Where's all this newfound interest in hash maps coming from? Once you hash something, you lose the prefix information, making it kinda' useless for this activity. Unless you create a hash for every string length variation... but
70.
by trentnelson 8y ago
> Could you get good-enough performance with something simpler and more portable? Hmmm. Did you read the article? Any of the C versions are relatively simple and portable. They basically work the same as the assembly ones and give gre
71.
by trentnelson 8y ago
The initial length + unique character test allows us to negative match in a way that is effectively identical to a bloom filter. If the initial negative match test indicates no match, then we can be certain there is not a match. Otherwise,
72.
by trentnelson 8y ago
I can't see how this avoids needing to do a comparison against the string in the slot once you've actually found the index though. I think I need to see this in C or asm to grok what the benefits are.
73.
by trentnelson 8y ago
I only submitted one of those about two weeks ago, if that’s any consolation :-)
74.
by trentnelson 8y ago
I bought a bunch of assembly/MASM books from the 90s recently, if that helps. Writing assembly is a skill that atrophies so quickly without constant exercise, so once you spool up to an acceptable level of assembly productivity, you r
75.
by trentnelson 8y ago
Heh, “predict the shit out of”, I like that.
76.
by trentnelson 8y ago
I think with SIMD type stuff and small data sets (e.g. <=16 strings), conventional big-O complexity analysis can leave a bit to be desired. Similarly, with SIMD and small data sets, you’re going to be faster than anything involving a poi
77.
by trentnelson 8y ago
Well... I mean the first version (IsPrefixOfStringInTable_1) uses the lengths from the string array to improve performance versus the baseline: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... The super-
78.
by trentnelson 8y ago
PEXT is pretty cheap... but, I still don't think I understand how what you're suggesting could optimally apply to prefix matching against all 16 strings at once, or why it would offer a substantial speed-up to the approach I'
79.
by trentnelson 8y ago
Sure am!
80.
by trentnelson 8y ago
Yeah I generally agree with regards to throttling/caps/license issues, especially re: AVX-512. AVX and AVX2 aren't too bad though. I'm not using computationally-intensive AVX instructions, just your standard vectorized
81.
by trentnelson 8y ago
Yeah it's actually a pretty inconsistent mish-mash of ISA usage. I could go straight SSE4.x but I'd lose out on the vp* goodies you get with AVX and AVX2, even if I'm only using XMM registers. The "length of 16, num e
82.
by trentnelson 8y ago
Fun tidbits: a) I bombed, like, 6 coding interviews whilst writing this article. Two of them were related to string processing, too, which I thought was funny. (In a depressingly ironic kind of way.) No point, other than I seemingly suck
83.
by trentnelson 8y ago
Patches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I
84.
by trentnelson 8y ago
> Were there any particular reason why you chose 16-bytes instead of 32-bytes? Like maybe targeting AVX but not AVX2?? (Then again, I see a rare ymm register here and there... sooo... I guess I'm just a bit confused with the design
85.
by trentnelson 8y ago
I love tries for larger data sets, and have used them many times for longest prefix matching problems. However, they inevitably involve pointer chasing, are quite branchy, and not really amenable to SIMD optimizations. They also do not hav
86.
by trentnelson 8y ago
I'm optimizing for ultra low latency here; i.e. what's the absolute fastest I can detect a prefix match against this known string table? The final assembly version is down around the 6-20 cycle range, depending on what you'r
87.
by trentnelson 8y ago
Thanks! Joe Walnes should get credit for the underlying HTML and CSS and site design and whatnot... I lovingly pilfered[1] his websocketd[2] site a while back for PyParallel[3] and liked it so much I decided it to use it for this personal
88.
by trentnelson 8y ago
Sorting the strings by length, or lexicographical? Length sort wouldn't work for the prefix-oriented nature of the comparisons. Lexicographical sorting and a binary search involves pointer chasing, and doesn't provide any way to
89.
by trentnelson 8y ago
Side note: people have been inquiring how I made the diagrams and whatnot. I'll put a little section like that on the next article. For now though: The two main diagrams, depicting struct layout and then the 5-pane register walk thro
90.
by trentnelson 8y ago
The article is much longer than I originally anticipated. If you're looking for some good bits, you could probably jump straight to here: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... That discu

More ›