Opened 11 months ago

Last modified 7 weeks ago

#9159 new feature request

cmm case, binary search instead of jump table

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

Description

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 11 months ago.

Download all attachments as: .zip

Change History (7)

Changed 11 months ago by wojteknar

comment:1 Changed 11 months ago by simonpj

That is toChunk3#?

Would you like to offer a patch?

Thanks

Simon

comment:2 Changed 11 months 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 11 months ago by rwbarton

  • Type changed from bug to feature 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 11 months ago by wojteknar

  • Priority changed from low to lowest

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 10 months 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 7 weeks ago by rwbarton

Note: See TracTickets for help on using tickets.