Statistical analysis of functional data structures

[Anton Tayanovskyy]

Hi,

Does anyone on the list has experience tuning purely functional maps/sets for a specific load? My current interest is in seeing if something can be done to the data structures used by F# compiler to speed up the compilation process.  When the computational complexity is fixed, there are still the constant factors to think of. When comparing two implementations with same complexity properties, the usual benchmarks seem a bit ad-hoc. I wonder if there is any work that uses statistics to hypothesize a certain input distribution and compute expected (rather than worst-case) time, and is there work on analyzing common kinds of load for different applications?

I tried the usual searches and asking this question on SO but with little success:

http://stackoverflow.com/questions/15839227/statistical-performance-of-purely-functional-maps-and-sets

The only papers I found online (and then was suggested to look at by the SO commenter) is by 1998-2000 work by Graeme Moss and Colin Runciman. At a first glance it does not look too bad and it puts forward a framework for designing benchmarks informed by a particular practical applications - so far so good, and I will try to study it in more detail. But is there anything more recent? Anyone has personal experience tuning DSs? 

Thanks,

--A

[Jon Harrop]

 

I think this is a very difficult thing to do. I once wrote a HashSet data structure in F# that used tries. You could tune the relative performance of construction and searching by altering the branching factor. Even in the OCaml Set you can alter it to some degree by adjusting the rebalancing criterion. However, even with one relatively-simple knob it is very difficult to benchmark thoroughly enough to draw any strong conclusions. The performance of my HashSet varies tremendously from one element type to the next.

 

Cheers,

Jon.

--
You received this message because you are subscribed to the Google Groups "Pragmatic functional programming research" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pragmatic-functional-progr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Anton Tayanovskyy]

Thanks.

Yes, it seems the problem is not defined well enough to study, nobody
is answering that SO question, perhaps it is after all not a valid
question..

I have not checked any of this yet, but I am secretly hoping for some
very basic "kitchen-sink" statistical results. City, file and many
other structure sizes have Pareto or Zipf (power law) distributions.
It is plausible that data encountered by functions at runtime would
have similar characteristics. The problem is of course, when designing
general-purpose collections we're averaging over many very different
applications. Still it would be nice to know at least something - for
example, that in the universe of all uses of F# Map.* module, say
Map.add, on all machines on planet Earth, the size of the input Map
seems to follow a power law.

That'd be neat since we would by default design benchmarks to draw
input values from a power law. Not sure if that's state of the art
right now.

Of course once you go down that road it's impossible to say where you
should stop.. As you point out, element types affect performance, etc.

--A

--
Kind Regards,
Anton Tayanovskyy

WebSharper™ - type-safe JavaScript in F#
http://intellifactory.com

[Jon Harrop]

Interesting question about the distribution of sizes of Maps in real
programs. I think the decay is probably faster than power law and probably
at least exponential (like the decay of lifetimes in programs according to
early research on generational GCs). Purely functional collections like
list, set and map are usually very small and often empty.

Cheers,
Jon.

WebSharperT - type-safe JavaScript in F# http://intellifactory.com

[Anton Tayanovskyy]

Very possible. However from what I read on the ubiquity of power-laws
in nature, they are often confused with exponential distribution, and
often the power law is not a good approximation in the lower range,
but is for the tail - so the "catastrophic" huge events are much more
likely than otherwise. But since small values dominate, to distinguish
the two with any confidence you need a very large sample.

This is probably too much refinement for benchmark design. If either
is the case with actual data, comparing two implementations based on a
benchmark where inputs are drawn from an exponential distribution is
likely to be a lot more helpful - compared to using a uniform
distribution anyway.

I toyed with the idea of instrumenting the F# compiler bootstrapping
process to collect data on Map.* usage and having a look at it - just
have not found time to do it yet. Of course that would be very
application-specific, but still interesting.

Thanks,

--A

WebSharper™ - type-safe JavaScript in F#
http://intellifactory.com

[Jon Harrop]

I've done some work related to this since then...

I wrote the Set and Map benchmarks used for the F# compiler a few years ago and one of the most important lessons I learned is that the performance of Set and Map operations under controlled conditions bears no resemblance to their performance in the wild. In other words, the time taken to do an insertion, deletion or search in a tight loop is a poor predictor of the performance of any non-trivial algorithm (e.g. graph algorithms) written using those operations. The reason is, I believe, that garbage collection obfuscates the cost and, in particular, the cost with generational GCs on modern machines is completely dominated by survivors: evacuation by physical copying is very expensive (which makes me think generational GCs are ripe for abandonment now).

I have also had a couple of weird and wonderful ideas that are laterally relevant:

Firstly, I developed what I call a "concestor dictionary" which is a mutable hash table with purely functional diffs to all live references. Provided a program acts upon the same version of a dictionary over and over again the operations will be applied to the mutable hash table and, consequently, can be expected to run much faster than any purely functional dictionary. If/when a program recovers a previous version (e.g. backtracking) the purely functional diff is applied to the mutable dictionary to make it reflect the new current version of the dictionary. Despite the huge performance advantages of mutable hash tables over immutable trees it turns out that this approach is no faster than using a purely functional tree (at least on my benchmarks). My intuitive interpretation of this result is that the cost of purely functional dictionaries is dominated by supporting persistence even if it isn't used. Incidentally, I called it a concestor dictionary because garbage collection must find the concestor of all live references and regard all ancestors of the concestor as eligible for collection (which is no easy task!) because backtracking can never require them.

Secondly, rebalancing can be delegated to another thread. For example, the main thread might insert an element into a purely functional set, creating new unbalanced branches in the tree and notifying a background thread that they require rebalancing. The background thread can rebalance the tree independently. Note that synchronisation is not required during rebalancing because racing to read and write equivalent trees is benign.