Hi, On Mon, Mar 5, 2012 at 1:55 PM, Marcel Reutegger <[email protected]> wrote: >> On a related note, I think it would be useful to tie orderability and >> SNSs together, as any code that implements SNSs should fairly easily >> be able to give us orderability as well. Thus I think it would be a >> good solution to implement both either below or above the MK level. >> Splitting the features across the MK line doesn't seem that useful. > > Isn't orderability a prerequisite for SNS?
Yes. My reasoning is as follows: a) If SNS support is added on top of an implementation that's *not* orderable, the SNS code needs to maintain an extra ordered list of name->mangled-name mappings for both orderability and SNS support. b) When implementing SNS on top of an orderable implementation (i.e. one that maintains an internal list of name->child mappings), the SNS code in any case needs a similar extra data structure, at least a name->mangled-name[] mapping or an equivalent alternative. The added complexity of a) vs. b) seems fairly small (i.e. much smaller than having a separate implementation elsewhere), which suggests that implementing orderability together with SNS would make sense. Alternatively, when you implement orderability on the storage level, you need to maintain some form of an ordered list of name->child mappings. Adding SNS support there is basically a matter of allowing a single name to occur more than once in that list. The extra complexity of merging concurrent changes needs to be implemented in any case regardless of where in the stack orderability and SNS are implemented. I believe that also there it would be useful if the merge algorithm was able to consider both these features at the same time and level. BR, Jukka Zitting
