bsearch.cpp

  /* std::lower_bound + hand-written move */

  void insert(Index x) {
    auto it = std::lower_bound(begin(), end(), x);
    if (it == end()) push_back(x);
    else if (*it > x) {
      Index i = it - begin();
      resize(size() + 1);
      for (Index j = size() - 1; j > i; j--) {
        (*this)[j] = (*this)[j - 1];
      }
      (*this)[i] = x;
    }
  }

  bool erase(Index x) {
    auto it = std::lower_bound(begin(), end(), x);
    if (it != end() && *it == x) {
      for (Index j = it - begin() + 1; j < size(); j++) {
        (*this)[j - 1] = (*this)[j];
      }
      resize(size() - 1);
      return true;
    }
    return false;
  }

  bool has(Index x) {
    auto it = std::lower_bound(begin(), end(), x);
    return it != end() && *it == x;
  }
  
  /* std::lower_bound + std::move + std::move_backward */
  
  void insert(Index x) {
    auto it = std::lower_bound(begin(), end(), x);
    if (it == end()) push_back(x);
    else if (*it > x) {
      Index i = it - begin();
      resize(size() + 1);
      std::move_backward(begin() + i, begin() + size() - 1, end());
      (*this)[i] = x;
    }
  }

  bool erase(Index x) {
    auto it = std::lower_bound(begin(), end(), x);
    if (it != end() && *it == x) {
      std::move(it + 1, end(), it);
      resize(size() - 1);
      return true;
    }
    return false;
  }

  bool has(Index x) { // same
    auto it = std::lower_bound(begin(), end(), x);
    return it != end() && *it == x;
  }

result.md

Built with -O2 and run with bin\wasm-opt banana.wast -O --debug.

linear search + hand-written move (original)

Test	coalesce-locals	Total
1	3.43754	7.40638
2	3.57819	7.96062
avg	3.507865	7.6835

std::lower_bound + hand-written move

Test	coalesce-locals	Total
1	3.53688	7.53702
2	3.41175	7.2713
3	3.32817	7.38682
avg	3.4256	7.39838

std::lower_bound + std::move + std::move_backward

Test	coalesce-locals	Total
1	3.28129	7.43767
2	3.30874	7.2682
3	3.26425	7.42072
avg	3.28476	7.37553

For some reason I do not understand, <chrono> is not working properly for me. Each test actually took me about 15 minutes to run, but wasm-opt reported it was just 7.x seconds. Probably a mingw-w64 gcc compiler issue rather than the code because I once compiled older version of binaryen with MSVC and the time reported by wasm-opt is correct. Please only compare the result above relatively.

Edit:
I just compiled it with MSVC, same result.

15 minutes is surprisingly slow, but --debug is expected to be fairly slow, as it does heavy validation and debugging-helping operations. Perhaps we should have an option to get timing info without that. But, the timing info ignores the validation overhead.

I run bin\wasm-opt banana.wast -O (without --debug), it only took about 7-8 seconds, so the result is correct. The rest of the 15 minutes must be spent on validation and other debugging steps.