Of knapsacks and language features

Joe Darcy Joe.Darcy at Sun.COM
Thu Apr 2 21:30:57 PDT 2009

A quick note on some additional considerations in language feature 

I view the selection of language proposals to be a kind of knapsack problem:


That is, each feature has some discrete size and complexity to implement 
and confers some improvement to the language.  There is a bounded size 
and complexity budget and the goal is maximizing the value held in the 
knapset, the value of improvements shipped in a release.

Of note is that implementing a language change has much more of a 
discrete size (or a small selection of possible sizes) rather than a 
continuous range of possible sizes.  In other words, because of the 
coordinated set of deliverables associated with a language change, it 
may be reasonable to implement 0% 50% or 100% of a possible feature but 
no other fraction.  And doing 50% of the feature might take 1/4 of the 
effort of doing the whole thing or 3/4 of that effort.

Even when precise costs and improvements can be quantified, because of 
these discrete sizes the "greedy" algorithm of putting the highest value 
/ cost item in the knapsack first can lead to globally poor results.

If nothing else, having a pre-pass to reduce the number of proposals 
being considered for further review greatly reduces the combinatorial 
possibilities of subsets of features that could be included in a release.


More information about the coin-dev mailing list