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
selection.
I view the selection of language proposals to be a kind of knapsack problem:
http://en.wikipedia.org/wiki/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.
-Joe
More information about the coin-dev
mailing list