wasm-micro-runtime
wasm-micro-runtime copied to clipboard
bytecodealliance
Fix quadratic runtime for duplicate export name detection
Previously, the loader would check the name of a new export against all existing exports, leading to a quadratic running time.
This change makes the loader parse the entire export section. The exports are then sorted by name, then adjacent exports are checked for uniqueness. Export order is preserved.
In a module with 100,000 exports, the load time goes from 20+ seconds to a couple hundred milliseconds on my machine. In the case of 10,000 exports, it's a couple hundred milliseconds down to tens of milliseconds.
This change will qsort the array once at the end of export section loading.
I was initially hoping that sorting the exports themselves by name would allow a binary search implementation in all the wasm_runtime_lookup_... functions, but as you observed in #3407, this causes other problems. Your solution would require keeping 2*ExportCount pointers in memory while the module is loaded, is this OK?
In a module with 100,000 exports, the load time goes from 20+ seconds to a couple hundred milliseconds on my machine. In the case of 10,000 exports, it's a couple hundred milliseconds down to tens of milliseconds.
This change will qsort the array once at the end of export section loading.
OK, got it, it really improves a lot. It only allocates memory one time and qsort the array one time.
I was initially hoping that sorting the exports themselves by name would allow a binary search implementation in all the
wasm_runtime_lookup_...functions, but as you observed in #3407, this causes other problems. Your solution would require keeping 2*ExportCount pointers in memory while the module is loaded, is this OK?
Keeping 2 * export_count pointers really consumes a lot of memory. IIUC, maybe we can just use a uint32 array (e.g. uint32 *export_iths_of_sorted_name) to save each export's ith of a temporary sorted export array, which is sorted by name. And then use binary-search to lookup to export, and get the export name with exports[export_iths_of_sorted_name[i] in the lookup.
@sjamesr I got an idea to improve the performance of wasm_runtime_lookup_function and submitted PR #3865, could you help check it? Thanks.
#3865 was more like my first approach of sorting the exports in place, but I couldn't figure out why the CI was failing. You've fixed that, so I think that approach is obviously better
#3865 was more like my first approach of sorting the exports in place, but I couldn't figure out why the CI was failing. You've fixed that, so I think that approach is obviously better
But #3865 only optimizes wasm_runtime_lookup_function, it doesn't refine the wasm/aot loading process. I am not sure why you close this PR? The idea looks good.
I misunderstood your other change, I thought you had a better way to fix performance in the loader as well, I'll reopen this one and address your comments.
@wenyongh This should be good for another look, thank you for your comments