On Fri, Aug 27, 2010 at 4:47 PM, Ian Lance Taylor <i...@google.com> wrote: > "Paulo J. Matos" <pocma...@gmail.com> writes: > >> In the first case, it generates a binary tree, and in the second two >> jump tables. The jump tables solution is much more elegant (at least >> in our situation), generating less code and being faster. >> Now, what I am wondering is the reason why GCC doesn't try to cluster >> the cases trying to find for clusters of contiguous values in the >> switch. >> >> If there is no specific reason then I would implement such pass, which >> would before expansion split switches according to value clustering, >> since I find it would be a good code improvement. >> >> Currently GCC seems to only use jump table is the range of the switch >> is not much bigger than its count, which works well in most cases >> except when you have big switches with clusters of contiguous values >> (like the first example I sent). > > I don't know of any specific reason not to look for clusters of switch > cases. The main issue would be the affect on compilation time. If you > can do it with an algorithm which is linear in the number of cases, then > I think it would be an acceptable optimization.
In fact we might want to move switch optimization up to the tree level (just because it's way easier to deal with there). Thus, lower switch to a mixture of binary tree & jump-tables (possibly using perfect hashing). Richard.
