Opened 5 years ago

Closed 4 years ago

Last modified 3 years ago

#9159 closed feature request (duplicate)

cmm case, binary search instead of jump table

Reported by: wojteknar Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 7.8.2
Keywords: CodeGen Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #10137 Differential Rev(s):
Wiki Page:


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.

Attachments (1)

ChunkBinSearchNotJumpTable.hs (1.2 KB) - added by wojteknar 5 years ago.

Download all attachments as: .zip

Change History (9)

Changed 5 years ago by wojteknar

comment:1 Changed 5 years ago by simonpj

That is toChunk3#?

Would you like to offer a patch?



comment:2 Changed 5 years ago by wojteknar

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.

comment:3 Changed 5 years ago by rwbarton

Type: bugfeature request

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.

comment:4 Changed 5 years ago by wojteknar

Priority: lowlowest

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?

comment:5 Changed 5 years ago by arotenberg

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;

comment:6 Changed 5 years ago by rwbarton

comment:7 Changed 4 years ago by thomie

Resolution: duplicate
Status: newclosed

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

comment:8 Changed 3 years ago by simonpj

Keywords: CodeGen added
Note: See TracTickets for help on using tickets.