Need performance characteristics of operations (e.g. on strings)

[ezyang]

They're not on the Haddocks, because all the ops were hidden behind a type class. Not sure what a good way of handling this is, but maybe the type classes can say what the expected asymptotics are.

The most important higher order bit of information when it comes to packed representations is whether or not they share buffers internally (e.g., is splitAt an O(1) operation?) Based on code reading, it looks like foundation strings do; that's important to tell users.

[vincenthz]

I don't see a way to handle those informations at the moment. The type class are not meant to abstract over the difference of asymptotic behavior, but just provide a consistent set of feature. you can last on a list, or an array, or a map, or a trie, despite whether it make sense at the structure level to do so.

Ideally, I would imagine that one can switch from [] to Array to Map with foundation, just by changing a signature type and not changing any call, and that is the purpose of the typeclasses.

I suppose it's up to each types to describe itself enough so that people understand what the type is designed to be for (e.g. array fast o(1) lookup, map fast key lookup, etc.). Internally, where it would be allowed to call a type's functions directly, I guess it's useful to know about the function profile (memory consumption, asymptotic behavior, etc)

Related to the sharing buffer, I think it's going to be up to each type to describe how they work, and I think it's somewhat more critical.

In my case, I'm not sure the asymptotic information per call are relevant when I develop (on top of the typeclass interface), I usually trust my understanding of the structure I'm using and benchmarks when it come to make decision (and here being able to switch really fast between 2 different structures might be really cool).

[ezyang]

Fair enough, but the types in Foundation.String and Foundation.Array don't describe their characteristics ;)

[vincenthz]

Yeah I'm fairly aware. in an ideal situation they should, so eventually we'll get there hopefully.

[JanGe]

It would be nice to have a table comparing the characteristics of all Collection types we define in Foundation itself either inline in the Foundation.Collection haddocks or at least linked from there, similar to Scala's Performance Characteristics page that is linked from their API docs.

[vincenthz]

Somewhat close to what you're talking about :) but it's more a work in progress to see where to go with the different collection (and their properties) versus APIs:

https://github.com/haskell-foundation/foundation/blob/master/Collection.md

definitely agree with this anyway.