Skip to content
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

Optimize test for empty string #7061

Closed
vicuna opened this issue Nov 27, 2015 · 7 comments
Closed

Optimize test for empty string #7061

vicuna opened this issue Nov 27, 2015 · 7 comments

Comments

@vicuna
Copy link

vicuna commented Nov 27, 2015

Original bug ID: 7061
Reporter: @alainfrisch
Status: acknowledged (set by @damiendoligez on 2017-03-06T15:28:43Z)
Resolution: reopened
Priority: normal
Severity: feature
Category: middle end (typedtree to clambda)
Monitored by: @jmeber

Bug description

Currently, the expression (s = "") results in a C call, and even (String.length s = 0) results in two sequential reads (first the header, then the access to the last byte) plus some arithmetic. Both could be turned into a new primitive that would simply read the first word of the block and compare it with the representation of the empty string (0x03000000 on 32-bit, I guess). This is likely to give a good speedup for this common operation, and allow to use the nice form (s = "").

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: @damiendoligez

You have to read at least the header and the last byte. With your shortcut you get the wrong result for

    "\x00\x00\x00\x03abcd" = ""

So the best you can do is define a function

    let is_empty_string s = String.length s = 0

and rely on the inliner to do the right thing.

Also, you cannot use the verb "allow" without a direct object: allow to <do_something>.

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: @alainfrisch

Note that (match s with "" -> true | _ -> false) produces rather good code, but it still checks for the block size from its header, which is useless in this case.

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: @alainfrisch

Yes, of course, sorry... At least we could turn s = "" into String.length s = 0 automatically.

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: bvaugon

With this implementation of ((=) ""), the test ("\000\000\000\003blablabla" = "") returns true on 32b arch, no ?

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: bvaugon

Sorry, crossed messages.

@vicuna
Copy link
Author

vicuna commented Nov 27, 2015

Comment author: @alainfrisch

So I did some benchmarks with

let f1 x = x = ""

let f2 x = String.length x = 0

let f3 = function "" -> true | _ -> false


let () =
  let s = String.make 10 'c' in
  for i = 1 to 1000000000 do
    ignore (f1 (*resp f2, f3*)  s)
  done

ocamlopt (x86 32-bit):

 x = ""              : 2.95s
 String.length x = 0 : 0.36s
 match .. .with ""   : 0.70s

Converting from x = "" to String.length x = 0 seems to be a low-hanging optimization. Similarly, one could optimize comparison with a known string constant into the pattern matching (which is about 3 times faster, confirmed by other micro benchmarks).

@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

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

No branches or pull requests

1 participant