Thanks for all your work Nir!  I personally think the BFS approach is the best we've seen yet for this problem!

Having read the thread you linked to in full (ignoring the tagents  bikeshedding and mudslinging that went on there), it sounds like the general consensus is that we should take thread scheduling changes slowly and let the existing new implementation bake in the 3.2 release.  That puts this issue as a possibility for 3.3 if users demonstrate real world application problems in 3.2.

(personally I'd say it is already obvious that there are problems an wde should go ahead with your BFS based approach but realistically the we're still better off in 3.2 than we were in 3.1 and 2.x as is)