FranckQC edited a comment on pull request #10663: URL: https://github.com/apache/tvm/pull/10663#issuecomment-1073440581
Hi, Sorry I couldn't discuss this with you last Thursday/Friday. Thanks for improving the CSE! Yes, indeed, iterating through the hash table will not necessary lead to accessing its elements always in the same order. That's because the iteration order depends on the hashes (and we use `structural_hash` for that), which themselves are based on pointers, so different run will give different addresses, which will give different hashes, and thus a different order in which elements are accessed. I guess it is not an issue as far as the CSE is concerned, because after producing this hashtable, we use it to produce a vector of semantic entities (which are pairs <expr, count>). The main loop of the CSE will later iterate through the elements of this vector. But before that, this vector gets sorted by the size (called "complexity") of the expression (the first component). So the order of the end result (the vector) is non-deterministic only for elements with the same size / complexity, for which it does not matter (again, only for the CSE) in which order we common them. (i.e. it should not add or remove opportunities for commoning more later). Said differently, this non-determinism should appear for orthogonal choices. I guess as in: ``` Mem[i1] = (a+b)+ (c+d); Mem[i2] = a+b; // We can common this one before or after Mem[i3] = c+d; // this one, it does not matter for the CSE Mem[i4] = (a+b) + (c+d) + e; ``` for which we could produce: ``` let cse_var_2 = a+b in let cse_var_3 = c+d in let cse_var_1 = cse_var_2 + cse_var_3 in Mem[i1] = cse_var_1; Mem[i2] = cse_var_2; Mem[i3] = cse_var_3; Mem[i4] = cse_var_1 + e; ``` Or the alternative version were (c+d) gets introduced before (a+b). **In practice, what is chosen currently depends on the addresses of the free variables 'a', 'b', 'c' and 'd' because they are used for the hashes**. I did not think that having this level of non-determinism would be an issue, but you're clearly right that its better to always produce exactly the same resulting TIR code, that just makes testing easier. Sorry I did not think about it when I wrote it! Your way of making it deterministic (by first copying the hashtable into an array, which you then sort using the actual syntax that the expressions represent) is perfectly fine to me. According to the doc about `structural_hash` ( here : https://tvm.apache.org/docs/reference/api/python/ir.html ), it seems an alternative could have been to set its `map_free_vars` parameter to true, as that's the reason the hashes use pointers. If that was the only place were addresses are used in the hashes, it should make everything deterministic too. I'll see if that works too, out of curiosity. Many thanks for having spotted that and for having fixed it! Kind regards, Franck -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
