Skip to content

String Hash Switch Argument #1518

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
dOrgJelli opened this issue Oct 25, 2020 · 5 comments
Closed

String Hash Switch Argument #1518

dOrgJelli opened this issue Oct 25, 2020 · 5 comments
Labels

Comments

@dOrgJelli
Copy link

In order to enable string as a valid switch argument type, create a compile-time & run-time string hashing function. For example:

function efficientConditionalLogic(arg: string) {
  switch (arg) {
    case "constant": {
      // logic
    }
  }
}

would be interpreted by the compiler as:

function efficientConditionalLogic(arg: string) {
  const _1 = __hash(arg);

  switch (_1) {
    case 0x123...: {
      // 0x123... == __hash("constant")
    }
  }
}

where __hash is:

function __hash(str: string): u32 {
  // perform hash
}
@dOrgJelli
Copy link
Author

dOrgJelli commented Oct 25, 2020

@jtenner I don't know if your code sample is equivalent. In my current understanding, your code would result in run-time comparison of str and "constant", meaning it's just as slow as:

if (str == "constant") {
}

The goal is to avoid byte for byte comparison of a long string, and instead be able to compare two u32 hashes. While the hashing of the run-time value str is slower than a single mem compare, it is faster in a long list of switch statements:

switch (hash(str)) {
  // 20+ cases
}

*please correct if I'm incorrect

@jtenner
Copy link
Contributor

jtenner commented Oct 25, 2020

I made a mistake with the comment and deleted it. It wasn't relevant. One of the things you can do is apply an AST transform for TaggedTemplateLiterals:

switch(hash(str)) {
  case hash`constant string`:
}

I don't know if @dcodeIO has implemented the parser for TaggedTemplateLiterals, but that sort of thing could be incredibly helpful for devs.

@dcodeIO
Copy link
Member

dcodeIO commented Oct 26, 2020

Note that switching over hashed values will most likely not yield a br_table instruction, but rather a sequence of br_ifs since case values aren't dense enough. Also note that hashing alone may produce false positives, i.e. two strings producing the same hash code, so typically an additional check to tell collisions apart is necessary as well.

For strings specifically, some sort of multi-level table (switch on length and single chars before doing exact compare) might yield better results.

@MaxGraey
Copy link
Member

MaxGraey commented Oct 26, 2020

For strings specifically, some sort of multi-level table (switch on length and single chars before doing exact compare) might yield better results.

Yes, I remember we talked about this a while ago. The best approach is static trie (multi-level table) which also scales well from one char to many while hash apprach has a lot of disadvantages and also required special handling for one-char cases and collision resolving.

@stale
Copy link

stale bot commented Dec 19, 2020

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants