Rev 3.7 release with map/reduce; Python-like syntax

Revision 3.7 of the alpha release 0.5 of the ParaSail compiler and virtual machine is now available at the same URL we have been using recently:
 
    http://bit.ly/Mx9DRb

This release has a number of new features, including a special syntax for map/reduce style computations, filters added to iterators, and support for an optional Python-like syntax.  For a description and some examples of the new map/reduce syntax, see:

  http://parasail-programming-language.blogspot.com/2012/11/special-syntax-for-mapreduce-in-parasail.html

Here is a simple example using the map/reduce syntax (and a filter) to compute the square of N by summing the first N odd integers:

    func Square(N : Univ_Integer {N >= 0}) -> Univ_Integer is
        return (for I in 1 ..< 2*N {I mod 2 == 1} => <0> + I);
    end func Square;

Filters are mentioned in the above blog entry, and illustrated in the above example. Here is another example where a "functional" version of QSort uses filters with a triplet of container comprehensions.  The filters are immediately before the "=>", enclosed in {...}:

    
    func QSort(Vec : Vector<Element>) -> Vector<Element> is
        if |Vec| <= 1 then
            return Vec;  // The easy case
        else
            const Mid := Vec[ |Vec|/2 ];  // Pick a pivot value
            return 
                QSort( [for each E of Vec {E < Mid} => E] )  // Recurse
              | [for each E of Vec {E == Mid} => E]
              | QSort( [for each E of Vec {E > Mid} => E] ); // Recurse
        end if;
    end func QSort; 

Note that we have added a "magnitude" operator "|...|" which can be defined as appropriate for a given interface; for vectors |V| is equivalent to Length(V).

The ParaSail compiler now recognizes a Python-like variant, in addition to the "normal" ParaSail syntax. In the Python-like syntax variant, "is", "then", "of", and "loop" are replaced by ":"; semicolons are optional; "end if", "end case", etc. are not used. "end class", "end interface, "end func" are optional. Indenting is significant. There are also some Python-inspired synonyms: "def" may be used instead of "func"; "elif" may be used instead of "elsif"; "# " may be used instead of "//" to introduce a comment (notice the required space).

The Python-like syntax is best illustrated by example. Here is the same QSort function given above using the Python-like syntax:

    
    def QSort(Vec : Vector<Element>) -> Vector<Element>:
        if |Vec| <= 1:
            return Vec  # The easy case
        else:
            const Mid := Vec[ |Vec|/2 ]  # Pick a pivot value
            return 
                QSort( [for each E of Vec {E < Mid} => E] )  # Recurse
              | [for each E of Vec {E == Mid} => E]
              | QSort( [for each E of Vec {E > Mid} => E] )  # Recurse

Note that the above is strongly typed (unlike Python), but because of type inference on declarations, types only show up in the parameter and result types.

Currently the two syntax variants can be mixed and matched. At some point we may have some restrictions on mixing and matching. In any case semicolons will remain optional in both variants, and probably will start disappearing from examples given in future blog entries.

Both syntax variants are being supported at the moment as we are still ambivalent about whether the Python-like syntax is preferable. We have tentatively named this ParaSail-with-Python-like-syntax variant "PARython" or perhaps "Parython." We may be adding more scripting-oriented libraries so PARython might be usable in more contexts where Python is chosen today.

Special syntax for Map/Reduce in ParaSail?

The Map/Reduce operation has become widely known recently.  A traditional way of implementing a Map/Reduce operation is to pass to the map_reduce operation, a container such as a set, vector, or list, a mapping function which is applied to each element, and a reducing function which is used to combine two mapped elements into one result.  The mapping step is relatively straightforward, but the reducing step can come in various forms, as it depends on whether the reducing function is associative, commutative, symmetric, etc.  Most functional languages have at least two standard reducing mechanisms, often called foldl and foldr.  These differ in the way the elements of the sequence are combined, either starting at the left or starting at the right.  Typically there is also an initial value which most often corresponds to the identity element for the reducing function, and this becomes the result if the sequence is empty.  If there is no convenient identity element (such as for maximum), versions of foldl and foldr are provided that use the use the first or last element as the initial value (called foldl1 and foldr1 in Haskell), but then only work on non-empty sequences.  Here is the wikipedia entry on the various forms of fold/reduce:

    http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

Because ParaSail supports passing functions as parameters to other functions, Map/Reduce in all its forms can be supported in the "traditional" way.  The question is whether some alternative syntax might be useful as well, analogous to the special syntax provided for quantified expressions (which essentially use and or or as the reducing function over a set of boolean values), and for container comprehensions (which essentially use "|" as a reducing operation to combine values into a new container).  As examples, here is a ParaSail quantified expression that asserts an array is sorted:

  (for all I in 1 ..< Length(Vec) => Vec[I] <= Vec[I+1])

and here is a container comprehension that creates a vector of squares:

   const Squares : Vector<Integer> := [for I in 1..10 => I**2]

Quantified expressions and container comprehensions could also be implemented by passing functions as parameters, but clearly the special syntax makes it somewhat more convenient, and arguably easier to understand.  So the question is: is there an analogous situation for the general map/reduce operation?  Would a special syntax make it more convenient and/or easier to understand?

Here is an example using possible syntax for a general map/reduce:

   (for I in 1 .. Length(Vec) => <0> + Vec[I]**2)

This is to be interpreted as a map/reduce operation which produces the sum of the squares of the values of the Vec.  The initial result (in the case of an empty vector) is given inside the <...>, and then after each element is combined with the ongoing result, the new result replaces the <...> for the next element.  Here would be a dot product of two vectors (first we assert they are of the same length):

  {Length(Vec1) == Length(Vec2)}
 (for I in 1 .. Length(Vec1) => <0> + (Vec1[I] * Vec2[I]))

Here is a computation of factorial(N):

   (for I in 1 .. N => <1> * I)

If we wanted to compute the maximum of the elements of some function evaluated over a range of inputs, and we wanted to use the first value as the initial result (analogous to foldl1 in Haskell) we could write (after first asserting we have a non-empty set of inputs):

    {N > 0}
   (for I in 1 <.. N => Max(<F(1)>, F(I)))

This general syntax could be used with any ParaSail iterator, so if we wanted to count the number of symbols in a symbol table whose names are shorter than 3 letters, we could write:

   (for each S of Sym_Table => <0> + (Length(S.Name) < 3? 1: 0))

Here we might better use a filter annotation on the iterator (unfortunately, iterator filters are not yet implemented in the ParaSail compiler):

   (for each S of Sym_Table {Length(S.Name) < 3} => <0> + 1)
   
An explicit reverse or forward could be used with the iterator if we want to distinguish between foldr and foldl for reducing ordered sequences of values.  Otherwise, the default is an unordered parallel reduction.

Note that a quantified expression can be re-expressed in this more general map/reduce syntax.  For example, the above assertion of Vec being sorted could be re-expressed as:

   (for I in 1 ..< Length(Vec) => <#true> and then Vec[I] <= Vec[I+1])

Similarly, a container comprehension could be re-expressed using this general syntax.  For example, the table of squares could be re-expressed as:

   (for I in 1 .. 10 forward => <[]> | [I**2])

Overall this special syntax seems to provide a nice alternative for map/reduce.  In the traditional approach, we would have to "bundle" up the mapping and reducing operations into functions, whereas with this special syntax, we can write the operations directly in a relatively "normal" looking expression syntax.

We would appreciate comments on this proposed special map/reduce syntax.

Work Stealing Statistics; Qsort vs. N-queens

We recently added more statistics to the ParaSail interpreter that relate to work stealing (see recent blog entry about rev 3.5 release).  ParaSail uses work stealing to map the very light weight picothreads generated by the compiler, to the heavier-weight server threads which are provided by the underlying operating system, typically about one per physical core.  For more general information on work stealing, see:

   http://supertech.csail.mit.edu/papers/steal.pdf

Work stealing is a scheduling approach where each server thread has its own (double-ended) queue of picothreads.  When a server executing code spawns off another picothread, it is added to the end of that server's queue.  When a server finishes its current picothread and needs another one to execute, it removes the most-recently added picothread from its queue.  In other words, it uses a last-in, first-out (LIFO) discipline with its own picothread queue.  If at some point, the server finds its own queue to be empty, it looks around at other servers' queues, and if it finds one with some picothreads, it will steal a picothread from that queue.  However, in this case it will choose the oldest picothread, that is, it uses a first-in, first-out (FIFO) discipline when stealing from another server's queue.

So an interesting question is: When a server goes about picking a new picothread to execute, what proportion of the time does the server have to steal a picothread rather than simply pick one off its own queue?  We have added statistics to the ParaSail interpreter to determine this.  So the next interesting question is: Do all algorithms produce the same proportion of stealing, or does the stealing proportion vary significantly from one algorithm to another?

So here are some answers, based on having four server threads:

Qsort : Sort array of 500 randomly selected values between 0 and 99, twice:

  43139 thread steals out of 67096 total thread initiations;
 64.3% stealing proportion
 
N-queens: Generate all solutions to the N queens problem for 8x8 chess board, 6x6, and 4x4:

  1690 thread steals out of 25015 total thread initiations;
 6.8% stealing proportion

Quite a dramatic difference.

The classic (inefficient) recursive fibonacci produces an even smaller proportion of steals, for Fib(15):

  17 thread steals out of 986 total thread initiations;
 1.7% stealing proportion

We also collect statistics on how many of the servers are doing useful work on average, and how many picothreads are waiting on any server's queue, on average.  For these three cases, the averages are:
 Qsort:   3.45 servers active,  0.92 threads waiting for service
 N-Queens:3.89 servers active, 13.94 threads waiting for service
 Fib(15): 3.99 servers active, 17.99 threads waiting for service

We have also started collecting statistics about the proportion of allocations from regions that are performed by the server that created the region initially, versus by some other server (which presumably stole some work from the "owning" server).  This clearly reflects something about the work stealing, but also provides some additional information about what proportion of typical work is manipulating objects coming from an enclosing picothread, and how much is manipulating objects local to the scope of the picothread doing the work.   Here are the results for the above three test cases:
 Qsort:   64,578 non-owner allocs out of 445,479 = 14.5%
 N-Queens:29,489 non-owner allocs out of 115,586 = 25.5%
 Fib(15): [no allocations -- all objects were small]

So what about the algorithm determines the thread stealing proportion and/or the owner vs. non-owner allocations from a region?  Sounds like an interesting research project...

Rev 3.5 alpha 0.5 release of ParaSail

We just released a new version (3.5 alpha 0.5) of the ParaSail compiler and virtual machine, available at the same URL as before:

    http://bit.ly/Mx9DRb

We have added some improved statistics to the virtual machine interpreter related to work stealing and region usage, and a command "stats" to view the statistics without exiting the interpreter, and "stats clear" to view and zero-out the statistics.  We will shortly be posting another blog entry about some of the more interesting results of these new statistics.

Additional updates in this release:

• The conditional expression "(if X then Y)" is now equivalent to "(if X then Y else null)"
• We now use the "<|=" operator, if available, when building up an aggregate with an iterator inside, such as "[for I in 1..10 => I*5]".  Before we used the "var_indexing" operator instead if both "<|=" and "var_indexing" were available, using the value of "I" as the index.  This didn't make much difference when building up a vector, but was somewhat limiting in other cases.
• We now allow "reverse" when defining an aggregate with an iterator, such as "[for I in 1..10 reverse => I * 5]," allowing the creation of a reverse-order vector, for example.
• We have fixed a bug which meant that certain annotations were ignored if they immediately preceded or followed a call on an operation.

Strange Looping in St. Louis

I spent the last three days in St. Louis at the Strange Loop conference and the associated Emerging Languages Camp:

    http://thestrangeloop.com/

It was truly a great conference.  The two keynotes were exceptional.  Michael Stonebraker (of Ingres and Postgres fame) spoke about his new extraordinarily fast in-memory database VoltDB.  Jeff Hawkins (of Palm and "On Intelligence" fame) spoke about his theory of how the neocortex works, with special emphasis on Sparse Distributed Representations. He also talked about how his new company Numenta had figured out how to embody some of these theories in a program called Grok, which is actually useful for real-world problems such as predicting energy usage of a building twenty-four hours in advance, to allow for advance purchase of electricity at the best rates.

But it wasn't just the keynotes.  There was a wonderful grab-bag of talks on all sorts of subjects, from retargeting the Scala compiler to generate LLVM assembly language (rather than Java), to how Grand Central Dispatch works in iOS and Mac OS X, to ruminations on P vs. NP.  The crowd was heavily tilted toward functional programming, but there were still enough others around to keep things interesting.  And the forces for static typing vs. those for dynamic typing seem to have been closely matched in strength, so Scala and JavaScript were both very hot topics. 

I had presented on ParaSail at the prior Emerging Languages Camp, and that seemed to disqualify me from presenting again this year.  But I did lead a (very small) unsession on the use of region-based storage management for parallel programming.  One benefit was it forced me to coalesce ideas on why region-based storage management is an excellent alternative to a global garbage-collected heap in a highly parallel environment.  Slides from this unsession are available at:

   http://bit.ly/QB2o9G

All in all, these past three days were a great mind-expanding experience.  I encourage anyone who has the time, to make an effort to attend Strange Loop next year; I presume it will be at about the same time of year in St. Louis again.

Work stealing and mostly lock-free access

ParaSail uses work stealing to schedule the picothreads that make up a ParaSail program.  With work stealing, there are a relatively small number of heavy-weight worker processes, roughly one per physical core/processor, each serving their own queue of picothreads (in a LIFO manner), and periodically stealing a picothread from some other worker process (using FIFO, so as to pick up a picothread that has been languishing on the other worker's queue).  See the following blog entry for more discussion of work stealing:

http://parasail-programming-language.blogspot.com/2010/11/virtual-machine-for-parasail-with.html

What this means is that a worker's queue is referenced mostly by only one process, namely the owner of the queue.

A similar situation arises in the region-based storage management used in ParaSail.  A region is created when a new scope is entered, and most of the allocation and deallocation within a region is done by the worker that created the scope.  But due to work stealing, some other worker might be executing a picothread that is expanding or shrinking an object associated with the region, so some synchronization is necessary in this case.

So what sort of synchronization should be used for these situations where most of the access to a resource arises from an owning worker process, but some of the access arises from other non-owning workers?  We could use a traditional lock-based mutex all of the time, but this slows down the common case where all the access comes from the owner.  We could use a general N-way lock-free synchronization, but this generally requires some kind of atomic compare-and-swap and involves busy waiting.  Atomic compare-and-swap is not always available in a portable fashion at the high-level language level, and busy waiting presumes that there are never more worker processes than there are available physical processors/cores, so the current holder of the lock-free resource is actually making progress while other workers are busy-waiting.

So for ParaSail we are adopting a middle ground between fully lock-based synchronization and N-way lock-free synchronization, which recognizes the asymmetric nature of the problem, namely that one process, the owner, will be performing most of the references.  With the adopted solution, we only need atomic load and store, rather than atomic compare-and-swap, and there is never any busy waiting, so we can run on top of, for example, a time-slicing operating system, where some worker processes might be preempted.

So what is the adopted solution?  For a given resource, we have two flags which are atomic variables, one mutex, and a queue, named as follows:

• Owner-wants-resource flag
• Nonowner-wants-resource flag
• Resource mutex
• Nonowner-waiting queue

When the owner wants to use the resource:

• Owner sets the owner-wants-resource flag atomically;
• It then checks the nonowner-wants-resource flag:

•  If nonowner-wants-resource flag is set:
• Owner calls the mutex lock operation;
• Owner manipulates the resource;
• Owner clears the owner-wants-resource flag;
• <<Check_Queue>> Owner then checks the nonowner-waiting queue:
• If the queue is empty, it clears the nonowner-wants-resource flag;
• If the queue is not empty, it wakes up one of the waiting nonowners;

• Owner calls the mutex unlock operation (note that this might be combined with the above waking up of one of the nonowners -- e.g. using a lock handoff).

•  If nonowner-wants-resource flag is not set:
• Owner manipulates the resource;
• Owner clears the owner-wants-resource flag.
• Owner rechecks the nonowner-wants-resource flag:
• If nonowner-wants-resource flag is now set:
• Owner calls the mutex lock operation;
• Owner does the <<Check_Queue>> operation (see above);
• Owner calls the mutex unlock operation (note that this might be combined with the waking up of one of the nonowners by Check_Queue -- e.g. using a lock handoff).

When a nonowner wants to use the resource:

• Nonowner calls the mutex lock operation;
• Nonowner sets the nonowner-wants-resource flag atomically;
• Nonowner checks the owner-wants-resource flag;
• While owner-wants-resource flag is set:
• Nonowner adds itself to the nonowner-waiting queue;
• When woken up, reacquire the lock (or get lock automatically via a handoff from the process that woke us up);

• Nonowner manipulates the resource;
• Nonowner does the <<Check_Queue>> operation (see above);
• Nonowner calls the mutex unlock operation (note that this might be combined with the waking up of another nonowner by Check_Queue -- e.g. using a lock handoff).

How do we know this approach is safe?  We need to prove that the resource is never manipulated simultaneously by the owner and a nonowner.  This can only happen if the owner decides to not use the mutex, since otherwise the manipulation happens under protection of the mutex lock.  We know that the owner sets the owner-wants-resource flag before checking the nonowner-wants-resource flag, and similarly a nonowner sets the nonowner-wants-resource flag before checking the owner-wants-resource flag.  Therefore, if the owner decides to bypass the mutex, while a nonowner is going after the resource simultaneously, the nonowner must not yet have checked the owner-wants-resource flag (think about it!). If later the nonowner does reach the check on the owner-wants-resource before the owner is done, it will put itself onto a queue rather than immediately manipulating the resource.

How do we know this approach does not leave a nonowner waiting on the queue forever?  We know the owner rechecks the nonowner-wants-resource flag after clearing the owner-wants-resource flag, so the owner will never miss the possibility that a nonowner queued itself while the owner was manipulating the resource.

So what does this approach accomplish?  We see that the owner only uses a lock-based mutex when it bumps into a nonowner that is simultaneously manipulating the resource.  On the other hand, a nonowner always uses a lock-based mutex, and in addition it uses a queue if it happens to bump into the owner simultaneously manipulating the resource.  As mentioned above, this approach also avoids the need for atomic compare-and-swap, as well as avoiding the need for busy waiting.

ParaSail standard library prefix?

Due to popular demand, we are going to try to solidify and extend the ParaSail standard library.  One practical question is the naming convention for the ParaSail standard library.  C++ uses "std::" as the namespace for the standard library.  Java uses "java." or "javax." or "com.sun." or "com.oracle.".  C# (and .NET in general) uses "System." as the prefix.  Ada uses "Ada." (as well as "System." and "Interfaces.").

So here are some possibilities for ParaSail:

• Standard::
• System::
• ParaSail::
• PS::
• PSL::
• ??

I think I am currently favoring "System::" because ParaSail has those two upper case letters which would be a bit of a pain, and the others don't seem to capture the idea as well.  Note that we will probably arrange things so that you rarely need to write the "System::" prefix, but if there is ambiguity, then it would be necessary.

Comments?