R. A. Dehi @radehi@qoto.org
I read a lot. Sometimes I learn things. I like making things. I think reading and doing are complementary.
Joined Nov 2022
@SteveBellovin Oh no. Thank you for letting us know.
R. A. Dehi
boosted
@alcinnz Well, so, the effect of any finite-length string on a particular DFA is a finite map from possible states at the beginning of the string to resulting states at the end of the string. For the empty string it is the identity function.
You can compute the effect of a concatenation of strings by composing these maps. If you do this bottom-up on a long string, starting from all its one-character substrings and then consolidating them into a tree of substrings of length 2, 4, 8, etc., each exhaustively covering the original string, you have a log-time parallel algorithm for DFA evaluation on the string. The final step is to apply the finite map computed for the entire string to the initial state defined by the DFA.
Then, if desired, you can propagate the results back down the tree to find the state of the DFA at every character.
Is precisely the parallel prefix-sum algorithm, with the monoid operation being function composition rather than, for example, integer addition.
Does that make sense? I don't know how to evaluate the clarity of my explanation in part because I don't know how familiar you are with the background.
R. A. Dehi
boosted
"The whole problem with the world is that fools and fanatics are always so certain of themselves, but wiser people are so full of doubt." – Bertrand Russell, paraphrased from The Triumph of Stupidity”, Mortals and Others: Bertrand Russell's American Essays, 1931-1935
https://twitter.com/MNateShyamalan/status/1592287177542696963
@jeffjarvis Musk? Sure. The question is what is there after that. It still has a quarter billion daily active users; they won't disappear overnight, even if Twitter spends a week in the Fail Whale.
@freemo Of course not, it's full of 60s self-esteem rhetoric.
@abde RAII, the STL, arguably exceptions, and debugging other people's C++ code
Twitter nonsense
@mmasnick It sort of makes sense; certainly a lot of people don't think he should be in control of Twitter, including a lot of people who actually work at Twitter. Purges and unpredictable changes are par for the course when ruthless power struggles are afoot, and power (rather than profits) seems to be what Musk is after with his Twitter takeover, as he said in his TED interview. It remains to be seen how works out.
@mattblaze Yeah, it's pretty annoying.
@atomicpoet Hmm, sounds like I misinterpreted your post.
Twitter implosion
@mattblaze It'll be interesting to see what the new Twitter looks like six months from now.
@atomicpoet minor quibble, HTTP didn't exist until a decade after the internet's infancy
@alcinnz Sure, naturally.
@alcinnz It has some similarities to Tomasulo's algorithm, but Tomasulo's algorithm isn't SIMD.
@alcinnz A thing I've been thinking about for a while is heavy multithreading by enqueuing execution states in per-opcode queues, so that you can then do SIMD (or SIMT) execution of a single opcode in 64 or 128 concurrent execution states at once.
R. A. Dehi
boosted
Switched out Serial for PPP and ... we can now also use all the on device internet tools like it's 1999. Can telnet to the host with Hermes, so nothing lost.
It's broken. Nothing works. Everything wants https and 50MB downloads.
However this all works the way I want it now. Another revision of the lid and I'll print the final version.
@alcinnz BTW, to the extent that you can do opcode interpretation with array indexing, you can avoid the SIMT idle units problem; see the wc implementation in PoC||GTFO 21 for an example (returning to the earlier question of fast DFAs!)
@alcinnz No worries; was it understandable anyway? I meant N(N-1)/2.
@alcinnz How does #3 help if you have O(N^2) intersections "on" (really just above) that scanline? I agree that it should work fine most of the time because you usually have comparatively few intersections, but in those cases insertion-sorting an array of active lines will also work fine, and will probably be faster than maintaining a binary heap?
@alcinnz By the way, does your instance render the LaTeX in that toot?
I read a lot. Sometimes I learn things. I like making things. I think reading and doing are complementary.
Joined Nov 2022
