HN user
If I understand correctly, one of the challenges faced by this graph application relates to the workload being irregular and known only as the computation visits new parts of the graph. There's some work in this direction that might be helpful [1].
My favorite quote from Alan Perlis: “Symmetry is a complexity-reducing concept (co-routines include subroutines); seek it everywhere.”
The article makes for an interesting technical read, and points to some very important issues, such as debugging in a multicore environment.
Even so, I encourage anyone reading this article to keep in mind that there is a massive amount of work dedicated to software support for multicore parallelism.
For anyone interested in digging deeper into multicore parallelism, I recommend taking a look at the CMU approach to teaching algorithms [1]. They teach parallel programming to second-year undergraduates by default, and the students even write parallel implementations, which can achieve good parallel speedups on a multicore system.
Moreover, they do it using either a parallel functional language or a parallel library in modern C++.
Importantly, they get this far by largely hiding details of exactly how parallel tasks are scheduled across cores. There's a scheduler that does it, much like there's a garbage collector that frees unused memory in a memory-managed language.
I had the good fortune to be in Dybvig’s compilers class in the mid 2000s. The way it was presented really brought the concepts to life and made it enjoyable.
There's a fairly recent study looking into the cost of raising an interrupt. TLDR: the cost on conventional systems is quite high; a significant part of the cost can be eliminated by using a custom kernel; even with a custom kernel, there remains a substantial cost.
https://par.nsf.gov/servlets/purl/10079614
To my knowledge, the remaining cost could be decreased to approximately the same cost as a branch mispredict, but getting there would require changes to the chip hardware and software stack.
The Redex modeling tool [1] is an interesting point in this space. Its specialty is in making executable specifications of domain-specific languages. Redex models can be tested by the unit-testing framework of the Racket dialect of Scheme. There's plenty of excellent documentation on Redex, and it has some neat visualization tools. I've gotten plenty of value from using it for my research over the years, but suspect it'd be useful outside of academic research.
Here's a link to one lobbying org whose mission I believe in.
Great news!
I've been locked out of my Amazon account for a year now, for reasons I don't know. Amazon reps told me I'd hear back, but there's been nothing for months now. Fortunately, the credit card they have on file expired, and the ebooks I can no longer read are not so important to me. So, good riddance, I say.
What would concern me is, for example, if the cost of a transaction grows faster than the price of a given bitcoin in dollars. If that trend would continue for too long, then I suppose my bitcoin could get trapped in the system for an indefinite period of time, that is, from the time I no longer can justify moving the bitcoin because of high transaction fees to the time I can. It seems that this situation suggests a lower bound on the amount that makes sense to store in a bitcoin wallet. I wonder what that lower bound is today.
Thanks again! We're using the Expat license.
Thanks for the comment! We are using the MIT license. I've updated the source code in the git repository accordingly.
A few years ago, our research group published a data structure, called Chunked Sequence, that is similar to the Finger Tree. In short, Chunked Sequence features the same asymptotic profile as does Finger Tree (neglecting persistence) and, in addition, offers strong guarantees with respect to constant factors. Very roughly speaking, Chunked Sequence is to Finger Tree what b-tree is to red-black tree.
We've implemented Chunked Sequences as a package of C++ header files and provided source code on github. To the client, Chunked Sequence looks like STL deque, but with additional methods to allow split at a specified position and concatenate, both in logarithmic time. The operations which push and pop on the ends of the Chunked Sequence are approximately as fast as those of STL deque, and in certain use patterns much faster.