shwestrick

8 ms·

1.
by shwestrick 1y ago
I like this example. The client who didn't notice a difference would probably call it a bugfix. The client whose software got ever-so-slightly more reliable probably would call it a minor update. The client whose software previously wa
2.
by shwestrick 2y ago
Worth mentioning that you can always safely switch between AoS and SoA. Either can represent the other; all you've done is transpose the data. The same is not true of AoE/EoA. The AoE [Spam1, Egg1, Spam2, Spam3, Egg2] has no corre
3.
by shwestrick 2y ago
For those curious, this implementation is based on a recent line of research called "heartbeat scheduling" which amortizes the overheads of creating parallelism, essentially accomplishing a kind of dynamic automatic granularity co
4.
by shwestrick 2y ago
Nowadays 210 is actually parallel! You can run 210-style code using MaPLe ( https://github.com/MPLLang/mpl ) and get competitive performance with respect to C/C++. If you liked 210, you might also like https:/
5.
by shwestrick 2y ago
The two systems have very different tradeoffs. A few things in particular: * Separate compilation vs whole-program compilation. OCaml uses separate compilation and therefore has a very constrained heap object model which makes it possib
6.
by shwestrick 2y ago
I'm one of the authors of this work -- I can explain a little. "Provably efficient" means that the language provides worst-case performance guarantees. For example in the "Automatic Parallelism Management" paper ( h
7.
by shwestrick 3y ago
Enjoyed playing with this! N-queens search is another nice recursive example. E.g. call this with nqueens(0, 5, []) function nqueens(i:number, n:number, queens: number[][]) { if (i >= n) return 1; let count = 0;
8.
by shwestrick 3y ago
On modern multicore hardware this will be memory-bound; the amount of computation per byte is pretty small (just a few arithmetic instructions on average). My intuition is that the single scan will be faster because it requires a much small
9.
by shwestrick 3y ago
It's worth noting that you can solve these linear recurrences, `x(t) = a(t)x(t-1) + b(t)`, using a single parallel prefix sum where the elements are the input tuples `(a(t), b(t))`. The following operator called `combine` works. It&#x2
10.
by shwestrick 3y ago
Tons and tons of parallel algorithms use prefix sums. Typically the most common use is to compute a collection of offsets in parallel. Some examples: - compact a hash table (i.e., remove the empty slots) - flatten a jagged 2D array - rewrit
11.
by shwestrick 3y ago
Parallelism is only about performance, that's it. If you need something to go faster, parallelism is an option. Looking into the future, parallelism is one of the only remaining techniques for scaling classical computing. Processors ha
12.
by shwestrick 3y ago
It's a doctoral degree with a heavy emphasis on pedagogy and teaching. From https://www.cmu.edu/math/grad/phd/index.html : > The Doctor of Arts degree shares all requirements and standards with the Ph.
13.
by shwestrick 3y ago
More and more people nowadays are programming at high levels of abstraction. If you're designing the frontend of a website, or making a mobile game, or developing a stock trading algorithm, or whatever else, then you probably don'
14.
by shwestrick 3y ago
in latex, when typesetting math, by default, parentheses (and other brackets) are always a constant height. So if you put something which is taller than one line in between parentheses, it will look strange, with the content sticking out pa
15.
by shwestrick 4y ago
Some of us are still using SML for research and teaching, e.g. https://github.com/mpllang/mpl
16.
by shwestrick 4y ago
That's not a useful perspective. It doesn't matter what the goal of the law is; it matters what effect the law has.
17.
by shwestrick 4y ago
You seem to be interested in this question: "If I bike without a helmet, how much more likely am I to be injured than if I bike with a helmet?". And of course, the answer is that you are safer with a helmet. But the article is int
18.
by shwestrick 4y ago
Private deques can still be very effective for work-stealing, both in theory and practice! This paper comes to mind: https://hal.inria.fr/hal-00863028/document
19.
by shwestrick 4y ago
MLton also has perhaps the most impressive performance of any existing functional language implementation. It generates code that easily competes with hand-optimized low-level C/C++/whatever.
20.
by shwestrick 4y ago
When visiting vertices in parallel, there might be multiple potential parents that all attempt to visit the same vertex simultaneously. So, we need a way of picking which parent "wins".
21.
by shwestrick 4y ago
Perfect. Yes, that's exactly right -- if the language semantics is able to guarantee a set of possible values for a data-racy read, then it doesn't catch fire. The catch-fire terminology comes from the analogy that, as soon as a d
22.
by shwestrick 4y ago
That's a nice example. It seems that data races in Java don't "catch fire"; is that correct? The catch-fire problem is pretty bad for languages like C/C++, which have undefined behavior for data races, and in this s
23.
by shwestrick 4y ago
Ah I see. That's a fair point! When talking about this kind of stuff to people who are unfamiliar with, say, lock-freedom, I've found that "non-determinism" is too vague --- people start thinking about things like random
24.
by shwestrick 4y ago
Whoa, uhh, I mean, that's an extremely unfair and inaccurate characterization.
25.
by shwestrick 4y ago
Yes! It's a very similar idea. If I remember correctly, LVars are restricted enough to enforce determinism statically, which is quite nice.
26.
by shwestrick 4y ago
Author here. It all depends on what the goal is. If performance is the goal, then perhaps race conditions can be considered acceptable, if the gains are significant enough. I would hope that the primary takeaway from this post is that race
27.
by shwestrick 4y ago
Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctnes
28.
by shwestrick 4y ago
Follow-up question, assuming we define BB(n) = max number of 1s written to tape for a halting machine of n states. Does it make sense to compare BB(n) against A333479(n)? It seems like A333479(n) grows much faster... my mind is jumping to t
29.
by shwestrick 4y ago
Interesting. Is there a good motivation for using maximum normal form size, instead of number of steps (e.g. under left-to-right eager evaluation)? My first impression is that A333479(n) is not immediately comparable to BB(n), because of me
30.
by shwestrick 4y ago
and https://github.com/diku-dk/smlpkg !

More ›