cmm case, binary search instead of jump table

I'm not sure if this is qualifies as a bug or feature request.

For case expressions where the scrutinee is Int#,or Int, or probably anything else numerical, GHC generates binary search, where a jump table could easily be used instead. The functions toChunk1# and toChunk2# yield suboptimal code. I found a satisfactory workaround, toChunk3# uses Enum and it is fine.

For the attached code it probably does not matter much, but I have 65 cases in my real code, trying to implement a variant of ByteString, which will have the lowest possible storage overhead (just the info table pointer == one word) for lengths up to 64 bytes.

Trac metadata

Trac field	Value
Version	7.8.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	low
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 3

added Tbug Trac import labels

Attached file ChunkBinSearchNotJumpTable.hs ($990).

That is toChunk3#?

Would you like to offer a patch?

Thanks

Simon

That is toChunk3#?

I'm referring to the functions in the attached file.

Would you like to offer a patch?

Way beyond my skills, sorry.

Presumably the case on an Int# uses a binary search because there's no reason the cases need to be consecutive integers: imagine you change the last case to 1000000# -> Chunk08 w#. Now a jump table is not a good idea. The case on a Nat knows that the tag integer identifying the constructor will be in the range from 0 to 8.

We would need some heuristic for when to use binary search vs. a jump table (or perhaps both, if the cases to be matched consist of multiple ranges of consecutive integers). Maybe worth looking into what C compilers do.

Trac metadata

Trac field	Value
Type	Bug → FeatureRequest

changed weight to 0

Okay, this really is a corner case of case statement.

For one range the heuristics could be "fill factor". For multiple ranges it gets really difficult.

The workaround with Enum and tagToEnum# works fine. Perhaps I should just close this ticket?

Trac metadata

Trac field	Value
Priority	low → lowest

For comparison: The Java Virtual Machine has two instructions called tableswitch and lookupswitch, which are normally implemented as a lookup table and a binary search, respectively. Here is the code javac uses to decide whether to generate a tableswitch or lookupswitch for a switch statement:

// Determine whether to issue a tableswitch or a lookupswitch
// instruction.
long table_space_cost = 4 + ((long) hi - lo + 1); // words
long table_time_cost = 3; // comparisons
long lookup_space_cost = 3 + 2 * (long) nlabels;
long lookup_time_cost = nlabels;
int opcode =
	nlabels > 0 &&
	table_space_cost + 3 * table_time_cost <=
	lookup_space_cost + 3 * lookup_time_cost
	?
	tableswitch : lookupswitch;

mentioned in issue #10137 (closed)

Trac metadata

Trac field	Value
Related	→ #10137 (closed)

closed

This was fixed in #10137 (closed), to be released with ghc-8.0.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedDuplicate

mentioned in issue #13523

added runtime perf label

added Plow label