[GitHub] [orc] guiyanakuang commented on pull request #917: ORC-1008: Fix overflow detection code for C++ int64_t / java long

[GitBox <gi...@apache.org>]

guiyanakuang commented on pull request #917:
URL: https://github.com/apache/orc/pull/917#issuecomment-931871138


   > We may just need to do this -
   > 
   > *result = x * y; return (x == 0 || y == 0 || *result / x == y);
   
   `if (((value < 0 ? -value : value) | repetitions) >> 31 != 0 && r / repetitions != value)`
   The current is a copy of the JDK implementation, which intends that values in the range [-2^31, 2^31] can be short-circuited to determine that no overflow will occur. It is also assumed that this range is used more frequently.
   
   Thanks to @xndai for the advice, so I've done some simple benchmarking in https://quick-bench.com/.
   
   They perform about the same under higher versions of the compiler, and it seems that the current implementation is better under lower versions. 
   
   BM_A:  current impl
   BM_B:  advice impl
   BM_C:  __builtin_mul_overflow
   
   ![image](https://user-images.githubusercontent.com/4069905/135560227-ac184361-ff43-463e-9a95-9e6d6c2f02ad.png)
   ![image](https://user-images.githubusercontent.com/4069905/135560615-76c904a6-dbf8-4f58-a410-5a34368d9460.png)
   ![image](https://user-images.githubusercontent.com/4069905/135560675-49dd3d6e-41b0-4511-91d2-e17db29d3762.png)
   
   
   
   ```c++
   static bool multiplyExactA(int64_t value, int64_t repetitions, int64_t* result) {
     int64_t r = value * repetitions;
     if (((value < 0 ? -value : value) | repetitions) >> 31 != 0 && r / repetitions != value) {
       return false;
     }
     *result = r;
     return true;
   }
   
   static bool multiplyExactB(int64_t x, int64_t y, int64_t* result) {
     int64_t r =  x * y;
     if (x == 0 || y == 0 || r / y == x) {
       *result = r;
       return true;
     }
     return false;
   }
   
   static void BM_A(benchmark::State& state) {
     auto x = state.range(0);
     int64_t value;
     for (auto _ : state) {
       for (int64_t i = std::numeric_limits<int64_t>::min(); i < std::numeric_limits<int64_t>::max(); i += 1) {
         for (int64_t j = 2; j <= x; j += 1) {
           multiplyExactA(i, j, &value);
         }
       }
     }
   }
   
   static void BM_B(benchmark::State& state) {
     auto x = state.range(0);
     int64_t value;
     for (auto _ : state) {
       for (int64_t i = std::numeric_limits<int64_t>::min(); i < std::numeric_limits<int64_t>::max(); i += 1) {
         for (int64_t j = 2; j <= x; j += 1) {
           multiplyExactB(i, j, &value);
         }
       }
     }
   }
   
   static void BM_C(benchmark::State& state) {
     auto x = state.range(0);
     int64_t value;
     for (auto _ : state) {
       for (int64_t i = std::numeric_limits<int64_t>::min(); i < std::numeric_limits<int64_t>::max(); i += 1) {
         for (int64_t j = 2; j <= x; j += 1) {
           __builtin_mul_overflow(i, j, &value);
         }
       }
     }
   }
   
   BENCHMARK(BM_A)->Arg(512);
   
   BENCHMARK(BM_B)->Arg(512);
   
   BENCHMARK(BM_C)->Arg(512);
   ```


-- 
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: dev-unsubscribe@orc.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org