Review numeric range tree performance

[dranikpg]

Numeric range tree can have write performance issues with most likely a small set of different values.

dfly::search::RangeTree::SplitBlock takes up almost 90% of cpu time during insertions

[dranikpg]

func Period(p int, rdb *redis.Client) {
	start := time.Now()
	for i := range 100 {
		p := rdb.Pipeline()
		for j := 0; j < 1000; j++ {
			key := fmt.Sprintf("key%v:%v:%v", p, i, j)
			p.HMSet(ctx, key, "i", j%2)
		}
		p.Exec(ctx)
	}
	fmt.Println("Took", p, time.Since(start))
}

[dranikpg]

cumulative

Showing top 50 nodes out of 103
      flat  flat%   sum%        cum   cum%
     0.04s 0.064% 0.064%     57.69s 92.90%  [libboost_context.so.1.88.0]
         0     0% 0.064%     57.66s 92.85%  __invoke (inline)
         0     0% 0.064%     57.66s 92.85%  __invoke_impl (inline)
         0     0% 0.064%     57.66s 92.85%  boost::context::detail::fiber_entry (inline)
         0     0% 0.064%     57.66s 92.85%  fiber_entry
         0     0% 0.064%     57.66s 92.85%  invoke (inline)
         0     0% 0.064%     57.66s 92.85%  operator() (inline)
         0     0% 0.064%     57.66s 92.85%  run (inline)
         0     0% 0.064%     55.96s 90.11%  __apply_impl (inline)
         0     0% 0.064%     55.96s 90.11%  apply (inline)
         0     0% 0.064%     55.96s 90.11%  run_ (inline)
         0     0% 0.064%     55.34s 89.11%  std::function::operator() (inline)
         0     0% 0.064%     55.31s 89.07%  __invoke_r (inline)
         0     0% 0.064%     55.31s 89.07%  std::_Function_handler::_M_invoke (partial-inline)
         0     0% 0.064%     55.31s 89.07%  util::fb2::FiberQueue::Run
     0.02s 0.032% 0.097%     55.30s 89.05%  dfly::MultiCommandSquasher::SquashedHopCb
         0     0% 0.097%     55.23s 88.94%  dfly::Service::InvokeCmd
         0     0% 0.097%     55.22s 88.92%  dfly::CommandId::Invoke
     0.01s 0.016%  0.11%     55.22s 88.92%  dfly::HSetFamily::HSet
         0     0%  0.11%     55.22s 88.92%  fu2::abi_400::detail::type_erasure::erasure::invoke (inline)
         0     0%  0.11%     55.22s 88.92%  fu2::abi_400::detail::type_erasure::invocation_table::operator_impl::operator() (inline)
         0     0%  0.11%     55.22s 88.92%  fu2::abi_400::detail::type_erasure::tables::vtable::invoke (inline)
         0     0%  0.11%     55.21s 88.90%  absl::lts_20250512::FunctionRef::operator() (inline)
     0.01s 0.016%  0.13%     55.21s 88.90%  absl::lts_20250512::functional_internal::InvokeObject (inline)
     0.01s 0.016%  0.14%     55.21s 88.90%  dfly::Transaction::ScheduleSingleHop
         0     0%  0.14%     55.20s 88.89%  dfly::Transaction::Execute
     0.01s 0.016%  0.16%     55.20s 88.89%  dfly::Transaction::ScheduleInternal
         0     0%  0.16%     55.19s 88.87%  dfly::Transaction::ScheduleInShard
         0     0%  0.16%     55.17s 88.84%  dfly::Transaction::RunCallback
         0     0%  0.16%     55.16s 88.82%  InvokeObject
         0     0%  0.16%     55.16s 88.82%  dfly::(anonymous namespace)::OpSet
         0     0%  0.16%     54.54s 87.83%  dfly::ShardDocIndices::AddDoc
         0     0%  0.16%     54.51s 87.78%  dfly::ShardDocIndex::AddDoc
         0     0%  0.16%     54.42s 87.63%  dfly::search::FieldIndices::Add
     0.01s 0.016%  0.18%     54.39s 87.58%  dfly::search::NumericIndex::Add
         0     0%  0.18%     54.37s 87.55%  dfly::search::RangeTreeAdapter::Add
         0     0%  0.18%     54.36s 87.54%  dfly::search::RangeTree::SplitBlock
     2.89s  4.65%  4.83%     49.42s 79.58%  dfly::search::Split
         0     0%  4.83%     27.36s 44.06%  std::allocator_traits::construct (inline)
         0     0%  4.83%     26.11s 42.05%  absl::lts_20250512::InlinedVector::emplace_back (inline)
         0     0%  4.83%     26.11s 42.05%  absl::lts_20250512::InlinedVector::push_back (inline)
     0.04s 0.064%  4.90%     26.11s 42.05%  absl::lts_20250512::inlined_vector_internal::Storage::EmplaceBack (inline)
    22.90s 36.88% 41.77%     22.92s 36.91%  std::__new_allocator::construct (inline)
     3.20s  5.15% 46.92%     12.22s 19.68%  dfly::search::BlockList::Insert
         0     0% 46.92%     10.27s 16.54%  absl::lts_20250512::inlined_vector_internal::Storage::EmplaceBackSlow
     0.79s  1.27% 48.20%      8.84s 14.24%  absl::lts_20250512::inlined_vector_internal::ConstructElements (inline)
         0     0% 48.20%      8.05s 12.96%  absl::lts_20250512::inlined_vector_internal::IteratorValueAdapter::ConstructNext (inline)
     2.44s  3.93% 52.13%      6.63s 10.68%  dfly::search::SortedVector::Insert
        1s  1.61% 53.74%      4.85s  7.81%  dfly::search::BlockList::FindBlock

[dranikpg]

flat

Showing top 30 nodes out of 103
      flat  flat%   sum%        cum   cum%
    22.90s 36.88% 36.88%     22.92s 36.91%  std::__new_allocator::construct (inline)
     4.43s  7.13% 44.01%      4.45s  7.17%  std::pair::pair (inline)
     4.41s  7.10% 51.11%      4.41s  7.10%  _dl_mcount_wrapper
     3.44s  5.54% 56.65%      3.44s  5.54%  std::operator< (inline)
     3.20s  5.15% 61.80%     12.22s 19.68%  dfly::search::BlockList::Insert
     2.89s  4.65% 66.46%     49.42s 79.58%  dfly::search::Split
     2.64s  4.25% 70.71%      2.64s  4.25%  __madvise
     2.44s  3.93% 74.64%      6.63s 10.68%  dfly::search::SortedVector::Insert
     2.25s  3.62% 78.26%      3.75s  6.04%  dfly::search::BlockList::TrySplit
     1.70s  2.74% 81.00%      1.70s  2.74%  absl::lts_20250512::inlined_vector_internal::Storage::AddSize (inline)
     1.28s  2.06% 83.06%      1.28s  2.06%  io_uring_submit_and_get_events
        1s  1.61% 84.67%      4.85s  7.81%  dfly::search::BlockList::FindBlock
     0.80s  1.29% 85.96%      0.80s  1.29%  mi_block_set_nextx
     0.79s  1.27% 87.23%      8.84s 14.24%  absl::lts_20250512::inlined_vector_internal::ConstructElements (inline)
     0.78s  1.26% 88.49%      0.78s  1.26%  __gnu_cxx::__normal_iterator::__normal_iterator (inline)
     0.59s  0.95% 89.44%      0.59s  0.95%  __gnu_cxx::__ops::_Iter_less_iter::operator() (inline)
     0.54s  0.87% 90.31%      0.64s  1.03%  absl::lts_20250512::inlined_vector_internal::Storage::MakeStorageView (inline)
     0.53s  0.85% 91.16%      0.53s  0.85%  __gnu_cxx::__normal_iterator::operator++ (inline)
     0.44s  0.71% 91.87%      1.61s  2.59%  std::__unguarded_partition (inline)
     0.43s  0.69% 92.56%      0.43s  0.69%  std::swap (inline)
     0.41s  0.66% 93.22%      1.61s  2.59%  std::vector::insert (inline)
     0.36s  0.58% 93.80%      0.36s  0.58%  dfly::detail::ascii_unpack
     0.26s  0.42% 94.22%      0.67s  1.08%  dfly::search::BlockList::BlockListIterator::operator++ (inline)
     0.14s  0.23% 94.44%      2.34s  3.77%  std::vector::push_back (inline)
     0.07s  0.11% 94.56%      3.14s  5.06%  std::__uninitialized_copy_a (inline)
     0.07s  0.11% 94.67%      0.34s  0.55%  util::fb2::UringSocket::RecvMsg
     0.04s 0.064% 94.73%     57.69s 92.90%  [libboost_context.so.1.88.0]
     0.04s 0.064% 94.80%     26.11s 42.05%  absl::lts_20250512::inlined_vector_internal::Storage::EmplaceBack (inline)
     0.02s 0.032% 94.83%     55.30s 89.05%  dfly::MultiCommandSquasher::SquashedHopCb
     0.02s 0.032% 94.86%      2.20s  3.54%  std::vector::_M_realloc_append (inline)