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
performance bug in Interf #2470
Comments
Comment author: administrator
Unless I misunderstand you, my code did get rid of the bitmatrix in favor
Sure, I've attached two files. x86imkasm.ml is the one that stresses Let me know if there's any other information with which I can provide you! -reuben module M (R : Sledlib.RELOC_PRINT) = struct
|
Comment author: administrator
Yes, that's intentional. With a good hash function, it makes buckets
Indeed, that's a spectacularly poor choice for a hashing function :-(
Actually, I wonder if the redundant representation (adjacency lists + Would it be possible for you to send me the test file that stresses Thanks for your bug report,
|
Comment author: administrator Fixed by XL 2004-05-08 |
Original bug ID: 2470
Reporter: administrator
Status: closed
Resolution: fixed
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)
Bug description
Full_Name: Reuben Olinsky
Version: 3.07
OS: Linux
Submission from: roam191-29.student.harvard.edu (140.247.191.29)
I have an .ml file that takes more than 50 CPU seconds to compile on my
700 MHz computer with ocamlopt.opt version 3.07. The .ml file is
3253 lines long and machine-generated (more than 650 short functions
that look similar). I can provide it upon request...
I recompiled ocamlopt.opt, instrumented with gprof profiling, and found
out that about 82.6% of this compilation time (the 50+ seconds) was being
spent in Interf.find_in_bucket. This function seems to be the find
function for a resizable hash table that implements interference
graphs in the native-code compiler's Interf module. I've surmised the
following by reading through the implementation of these graphs...
The hash table resize operation is inefficient. Instead of re-hashing
all values, which might also be pretty slow, the table simply inserts
multiple copies of all elements in the hash table:
Because it doesn't figure out the actual hash values of elements at
array index n, it goes ahead and places extra copies of them at
array index oldtablesize+n.
Also, there appears to be an issue with the hash function itself:
It appears, dynamically, that most edges in this graph are between
nodes whose integer labels are close together (interferences
are most likely localized, right?). So the above hash function,
by simply XORing two values that are likely close together, does
not evenly distribute the keys (graph edges) along [0,hashtablesize).
I've confirmed this by manually instrumenting Interf and reading
output traces.
Although I'm not sure how good it is, I've put together a patch
that reduces the compilation time for the 50+ second test file
by more than half. I've essentially reimplemented the representation
of interference graphs in interf.ml, using an array of interval
'interval lists' (lists of closed intervals over integers).
The patch is included below but I make no guarantees about it;
it's worked fine for me, but I'm sure you're all much more
expert OCaml hackers and might be able to think of ways to
improve it. Feel free to e-mail me if you have any questions...
--
--- orig/interf.ml 2004-04-17 13:06:55.586572288 -0400
+++ patched/interf.ml 2004-04-17 13:07:18.662064280 -0400
@@ -21,46 +21,57 @@
module BitMatrix =
struct
Nil -> false
let rec set_in_ivallist j = function
let rec testandset mat i j =
if j > i then testandset mat j i else begin
let rec isset mat i j =
1))
let build_graph fundecl =
The text was updated successfully, but these errors were encountered: