Lambda the Ultimate

Personally, I would not place much emphasis on trees in the context of a highly parallel language.

First, note that you can do just fine using indices for references. You do not get automated garbage collection of your nodes this way, but you do get automated garbage collection of the tree as a whole.

Second, note that a lot of the benefits of using trees have to do with manipulating only one node at a time. This is a good way to waste time on a highly parallel machine -- in many practical cases you could probably rebuild the entire data structure represented by the tree in the time it takes to manipulate a few nodes.

That said, trees can be useful, once the data gets big enough. But in some contexts the best tree will be shallow with fat nodes (node size roughly comparable to some physical structure in your underlying parallel machine).

tl;dr: trees = Streetlight Effect

Typically I'd call that "no aliasing". The "no pointers" bit refers to the lack pointers as values, no pointer semantics - i.e. no ability to compare pointers or increment them. You have that too, of course.

Can you use the `reply` link near our names when replying to a comment?

[Thanks for the tip about the "reply" link.]

There is aliasing, in that A[I] and A[J] are aliased iff I == J, but none of what might be called "hidden" aliasing, where two different names or two different access paths end up on the same object. The point is that "pointer-free" implies quite a lot, and it isn't just a lack of shallow copying.

OK, from the example, this is a tree node:

class AA_Tree is
var Value : Element;
var Level : Univ_Integer := 0;
var Left : optional AA_Tree;
var Right : optional AA_Tree;
...


This makes sense as a way to organize certain kinds of data. It maps well to XML. There's a swap operation (atomic swap operations are nice to have available), so you can rearrange the tree in a controlled way.

But what if you want to move from a node towards the root? There's no "parent" relationship available. Of course, if you got to a node by recursive descent, there's an instance of the recursive function which has access to the parent, so you can find it that way.

The example for a directed graph gives every node a number, and then keeps sets of predecessor and successor node numbers in each node. The nodes themselves are simply "The vector of nodes, indexed by node ID." So this substitutes indices for pointers. A long time ago, I had to write things like that in FORTRAN. I've also done it in C++ when I had to represent arbitrary polyhedra in a dynamics simulator. It works well as long as you don't have to delete elements of the graph. Deleting isn't supported in the example given.

It does simplify memory management, though.

Deleting is pretty straightforward in the directed graph example provided, given that each node knows all of its predecessors and successors. After removing the node id from the corresponding sets of each successor/predecessor, setting the node to null would release all of its storage back to its region.

After deletion, the deleted node would still be in the vector of nodes. That node slot will not be reused, because Add_Node just adds a new node at the end of the vector of nodes. This creates a memory leak.

So now there's a need for a storage manager to reclaim nodes. Searching linearly for a node creates an O(n) overhead. Linking dead nodes together through their predecessor and successor sets would work. That's a standard storage allocator technique; it's an exercise in Knuth. Of course, this has to be done for each vector type. Maybe a vector type with reference counts and storage management primitives could be created.

This is the point at which the programmer wishes for a garbage collector.

Unfortunately there is no one perfect, general garbage collection algorithm, particularly when talking about a pervasively parallel language. In my experience, most of the time spent in garbage collection is worrying about objects that really ought to be stack temporaries in the first place. There are situations where you do a lot of insertions and deletions, and recycling the nodes is important, but that seems more the exception than the rule. Many data structures are built up, used, and then discarded.

In any case, the AA_Tree recycles nodes, and as you point out, it would be straightforward to have a directed-graph node deletion operation recycle nodes. Adding a set of "free" node-ids to the directed graph structure would be the simplest, allowing the free nodes themselves to be set to simply null on deletion.

I'm not quite sure I understand: what is the difference, wrt lack of pointers, between ParaSail and other languages such as Haskell?

I don't mean to imply that I think there isn't a difference, I just don't quite understand.

Functional languages have pointers, but if the objects are immutable, it doesn't really matter. However many so-called "functional" languages are not "pure," and they do have references to mutable objects (e.g the ML derivatives including OCaml, F#, etc.).

Haskell is to some degree the exception here, where it is a "pure" functional language. But then of course the IO monad is introduced to provide side-effects, and exactly how the IO monad plays with pervasive parallelism is an interesting question.

Bottom line is that ParaSail has many of the advantages of a pure functional language, while still allowing a more imperative style when appropriate. Note that if a ParaSail function has no "var" parameters, then it is essentially a "pure" function (since there are no global variables), so it should be possible (though not required) to write in a purely functional style in ParaSail.

Note that the current (version 3.0.1) implementation has essentially all of the "object-oriented" capabilities implemented, but does not yet include full support for passing operations as parameters. You can pass "polymorphic" objects and rely on dispatching to accomplish some of that (as in Java), but directly passing operations is still on the "soon-to-be-supported" list.

It clearly depends on how the graph is being managed. In many algorithms, it is quite possible for parts of the graph to be disconnected, and you wouldn't want disconnected parts to be automatically reclaimed. In general there is usually enough information already in the graph to support whatever kind of reclamation strategy is desired. If not, additional information can be added. In any case, setting any node to null will release all of its storage back to the associated region. This is analogous to the requirement to set a pointer to null if you want the GC to reclaim the designated object. And as a fall-back, when the region containing the graph goes out of scope, the entire region is automatically reclaimed.

I see. Lets hope it doesn't come up often enough.

How would you implement a symbolic simplifier or symbolic differentiation? If you do it naively by copying the subtree at each operation, you'll end up with asymptotically worse complexity (because each node is copied O(n) times where n is its depth in the tree). So would you represent a symbolic expression as an array of nodes, where each node again points into the array? How well does that work in practice? (how pretty/ugly is the resulting code?)

It is not uncommon to implement a kind of symbolic simplification using a "value numbering" approach, where there is a hash table that encodes computations, after first performing various canonicalizations and simplifications. In this sort of approach, you walk a tree and return a unique "value number" that represents it, where the value number is an index into this "computation table." This sort of technique maps quite directly into ParaSail. In general you don't have to think in terms of an "array of nodes," but rather an indexed container of nodes, which can grow and shrink as appropriate.

The main objection to manual memory management is that it's difficult to get right due to non-local interactions (e.g. framework callbacks, concurrency, etc.). It is often difficult to trace a memory leak to its source, or figure out how to correct it. It can also be difficult to manage concurrency, prevent use of deleted objects.

By comparison, management of an isolated structure representing a graph is easy. There are no complex interaction issues [assuming identifiers aren't remembered by the outside program]. It can be domain-specific, e.g. use a compacting copy-collection if that is appropriate (then swap or move). When developers forget to GC a long-lived structure representing a graph, it will be easy to trace the problem, and easy to fix it.

So, even if the scenario does come up, it doesn't cause very much pain. Especially compared to the pain of dealing with a malfunctioning GC...

Although you would think parallelism comes naturally to a pure functional language like Haskell, in fact it seems that it is not completely straightforward how to make the best use of parallel hardware in Haskell. The heavy use of lists in most functional languages is not particularly great for parallelism. Also most functional languages depend on underlying optimizations which break the pure side-effect-free model of computing, and so these optimizations can "fight" with the attempt to maximize parallelism. The net effect is that there are still major debates about the best way to handle parallelism in Haskell. The paper by Marlow et al from the Haskell '11 conference in Tokyo in September, "A Monad for Deterministic Parallelism," talks about some of the problems with the use of "par" and "pseq," and introduces a new monad called "Par." It seems clear that the parallel processing story for Haskell has not yet reached its final chapter.

In any case, as far as ParaSail, it adopts the "work stealing" model also used in Intel's Cilk language, and their Threaded Building Blocks (TBB) library. This model involves having a relatively small number of heavier weight "server" processes, each serving their own queue of very light weight threads (which we call "picothreads" in ParaSail, but they also go by other names like "sparks," "microthreads," lightweight threads, etc.). The approach starts with approximately as many server processes as there are physical cores. As a server executes a given picothread, it may spawn off many other picothreads. These are added to the servers own queue, which it serves in a last-in, first-out (LIFO) manner -- that is it serves the most recently spawned picothread first. However, if a server runs out of picothreads to serve, it looks around at the other servers' queues, and then "steals" a picothread from one of those, but in this case, it uses a first-in, first-out (FIFO) discipline, i.e., it steals the picothread that has been languishing longest on its server's queue.

This work-stealing approach does a very nice job of balancing the load, while preserving locality of reference. It works very well in the context of a language like ParaSail where the compiler automatically splits computations up into numerous picothreads, providing plenty of raw material for the work-stealing algorithm to do its thing.

This work-stealing approach does a very nice job of balancing the load, while preserving locality of reference.

Work stealing is being oversold by various PL designers. The locality of reference is great if you're doing a depth-first traversals with node-local references. As with "par" and other primitives, the program has to be refactored to make this true, or your speedups will be lousy. It is just one piece, and once you talk about locality, a very incomplete one.

I'll note right off that Haskell's parallelism doesn't seem to scale to a large number of cores. Now, this is implementation dependent, but the basic issue is that the following elements don't mix in a way that leaves me happy:

• stop-the-world collector
• Amdahl's law

Even for embarrassingly parallel computations, it can be difficult to get a speedup proportional to a very large number of cores because occasionally we must perform a world collection (which tends to get more expensive with more threads and cores active).

I think that ParaSail's control over memory can be a major contributor to keeping utilization high, albeit sometimes at the cost of a copy for large structures.