Base conversion of varint is inefficient

[spolitov]

While implementing sum for decimal, I tried a test of adding 1 to 1E123456 and noticed that during serialization, we convert a base10 varint with 123456 digits to a base 256 varint. This has been implemented using multiply and add and it is an O(n^2) algorithm where n is the number of digits.

yb::util::VarInt::ConvertToBase(int) const varint.cc:260
yb::util::VarInt::EncodeToTwosComplementBytes(bool*, unsigned long) const varint.cc:397
yb::util::VarInt::EncodeToTwosComplement(bool*, unsigned long) const varint.h:226
yb::util::Decimal::EncodeToSerializedBigDecimal(bool*) const decimal.cc:334
yb::QLValue::Serialize(std::__1::shared_ptr<yb::QLType> const&, yb::QLClient const&, yb::faststring*) const ql_value.cc:333
yb::ql::Executor::AggregateResultSets(yb::ql::PTSelectStmt const*) eval_aggr.cc:69
yb::ql::Executor::FlushAsyncDone(yb::Status const&, bool) executor.cc:1045
yb::internal::RunnableAdapter<void (yb::ql::Executor::*)(yb::Status const&, bool)>::Run(yb::ql::Executor*, yb::Status const&, bool const&) bind_internal.h:263
yb::internal::InvokeHelper<false, void, yb::internal::RunnableAdapter<void (yb::ql::Executor::*)(yb::Status const&, bool)>, void (yb::ql::Executor*, yb::Status const&, bool const&)>::MakeItSo(yb::internal::RunnableAdapter<void (yb::ql::Executor::*)(yb::Status const&, bool)>, yb::ql::Executor*, yb::Status const&, bool const&) bind_internal.h:920
yb::internal::Invoker<1, yb::internal::BindState<yb::internal::RunnableAdapter<void (yb::ql::Executor::*)(yb::Status const&, bool)>, void (yb::ql::Executor*, yb::Status const&, bool), void (yb::internal::UnretainedWrapper<yb::ql::Executor>)>, void (yb::ql::Executor*, yb::Status const&, bool)>::Run(yb::internal::BindStateBase*, yb::Status const&, bool const&) bind_internal.h:1222
yb::Callback<void (yb::Status const&, bool)>::Run(yb::Status const&, bool const&) const callback.h:493
yb::ql::QLEnv::FlushAsyncDone(yb::Status const&) ql_env.cc:210
yb::ql::QLEnv::FlushAsync(yb::Callback<void (yb::Status const&, bool)>*)::$_0::operator()(yb::Status const&) const ql_env.cc:178
boost::detail::function::void_function_obj_invoker1<yb::ql::QLEnv::FlushAsync(yb::Callback<void (yb::Status const&, bool)>*)::$_0, void, yb::Status const&>::invoke(boost::detail::function::function_buffer&, yb::Status const&) function_template.hpp:159
boost::function1<void, yb::Status const&>::operator()(yb::Status const&) const function_template.hpp:759
yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0::operator()() const batcher.cc:206
void std::__1::__invoke_void_return_wrapper<void>::__call<yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0&>(yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0&&&) type_traits:4291
void std::__1::__invoke_void_return_wrapper<void>::__call<yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0&>(yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0&&&) __functional_base:359
std::__1::__function::__func<yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0, std::__1::allocator<yb::client::internal::Batcher::RunCallback(yb::Status const&)::$_0>, void ()>::operator()() functional:1552
std::__1::function<void ()>::operator()() const functional:1903
yb::FunctionRunnable::Run() threadpool.h:479
yb::client::internal::Batcher::RunCallback(yb::Status const&) batcher.cc:208
yb::client::internal::Batcher::CheckForFinishedFlush() batcher.cc:201
yb::client::internal::AsyncRpc::Finished(yb::Status const&) async_rpc.cc:141
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&>(std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&&&) type_traits:4232
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&>(std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&&&) functional:2206
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&>(std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&&&) functional:2239
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&>(std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&&&) type_traits:4291
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&>(std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>&&&) __functional_base:359
std::__1::__function::__func<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status>, std::__1::allocator<std::__1::__bind<void (yb::client::internal::AsyncRpc::*)(yb::Status const&), yb::client::internal::ReadRpc*, yb::Status> >, void ()>::operator()() functional:1552
std::__1::function<void ()>::operator()() const functional:1903
yb::rpc::OutboundCall::CallCallback() outbound_call.cc:322
yb::rpc::OutboundCall::SetFinished() outbound_call.cc:404
yb::rpc::LocalYBInboundCall::Respond(google::protobuf::MessageLite const&, bool) local_call.cc:81
yb::rpc::YBInboundCall::RespondSuccess(google::protobuf::MessageLite const&) yb_rpc.cc:351
yb::rpc::RpcContext::RespondSuccess() rpc_context.cc:138
yb::tserver::RpcOperationCompletionCallback<yb::tserver::ReadResponsePB>::OperationCompleted() service_util.h:151
yb::tserver::TabletServiceImpl::Read(yb::tserver::ReadRequestPB const*, yb::tserver::ReadResponsePB*, yb::rpc::RpcContext) tablet_service.cc:1015
yb::tserver::TabletServerServiceIf::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) tserver_service.service.cc:141
yb::rpc::ServicePoolImpl::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) service_pool.cc:214
yb::rpc::ServicePool::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) service_pool.cc:279
yb::rpc::Messenger::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) messenger.cc:376
yb::rpc::Proxy::AsyncRequest(yb::rpc::RemoteMethod const*, google::protobuf::Message const&, google::protobuf::Message*, yb::rpc::RpcController*, std::__1::function<void ()>) proxy.cc:144
yb::tserver::TabletServerServiceProxy::ReadAsync(yb::tserver::ReadRequestPB const&, yb::tserver::ReadResponsePB*, yb::rpc::RpcController*, std::__1::function<void ()>) tserver_service.proxy.cc:45
yb::client::internal::ReadRpc::CallRemoteMethod() async_rpc.cc:534
yb::client::internal::AsyncRpc::SendRpcToTserver() async_rpc.cc:210
non-virtual thunk to yb::client::internal::AsyncRpc::SendRpcToTserver() async_rpc.cc:0
yb::client::internal::TabletInvoker::Execute(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, bool) tablet_rpc.cc:163
yb::client::internal::AsyncRpc::SendRpc() async_rpc.cc:121
yb::client::internal::Batcher::FlushBuffer(yb::client::internal::RemoteTablet*, std::__1::__wrap_iter<std::__1::shared_ptr<yb::client::internal::InFlightOp> const*>, std::__1::__wrap_iter<std::__1::shared_ptr<yb::client::internal::InFlightOp> const*>, bool) batcher.cc:539
yb::client::internal::Batcher::FlushBuffersIfReady() batcher.cc:487
yb::client::internal::Batcher::FlushAsync(boost::function<void (yb::Status const&)>) batcher.cc:244
yb::client::YBSessionData::FlushAsync(boost::function<void (yb::Status const&)>) session-internal.cc:133
yb::client::YBSession::FlushAsync(boost::function<void (yb::Status const&)>) client.cc:1391
yb::ql::QLEnv::FlushAsync(yb::Callback<void (yb::Status const&, bool)>*) ql_env.cc:178
yb::ql::Executor::FlushAsync() executor.cc:999
yb::internal::RunnableAdapter<void (yb::ql::Executor::*)()>::Run(yb::ql::Executor*) bind_internal.h:149
yb::internal::InvokeHelper<false, void, yb::internal::RunnableAdapter<void (yb::ql::Executor::*)()>, void (yb::ql::Executor*)>::MakeItSo(yb::internal::RunnableAdapter<void (yb::ql::Executor::*)()>, yb::ql::Executor*) bind_internal.h:886
yb::internal::Invoker<1, yb::internal::BindState<yb::internal::RunnableAdapter<void (yb::ql::Executor::*)()>, void (yb::ql::Executor*), void (yb::internal::UnretainedWrapper<yb::ql::Executor>)>, void (yb::ql::Executor*)>::Run(yb::internal::BindStateBase*) bind_internal.h:1078
yb::Callback<void ()>::Run() const callback.h:411
yb::cqlserver::CQLInboundCall::TryResume() cql_rpc.cc:311
yb::cqlserver::CQLServiceImpl::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) cql_service.cc:121
yb::rpc::ServicePoolImpl::Handle(std::__1::shared_ptr<yb::rpc::InboundCall>) service_pool.cc:214
yb::rpc::(anonymous namespace)::InboundCallTask::Run() service_pool.cc:252
yb::rpc::TasksPool<yb::rpc::(anonymous namespace)::InboundCallTask>::WrappedTask::Run() tasks_pool.h:70
yb::rpc::(anonymous namespace)::Worker::Execute() thread_pool.cc:98
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&>(std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&&&) type_traits:4232
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&>(std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&&&) functional:2206
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&>(std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&&&) functional:2239
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&>(std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&&&) type_traits:4291
void std::__1::__invoke_void_return_wrapper<void>::__call<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&>(std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>&&&) __functional_base:359
std::__1::__function::__func<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&>, std::__1::allocator<std::__1::__bind<void (yb::rpc::(anonymous namespace)::Worker::* const&)(), yb::rpc::(anonymous namespace)::Worker* const&> >, void ()>::operator()() functional:1552
std::__1::function<void ()>::operator()() const functional:1903
yb::Thread::SuperviseThread(void*) thread.cc:602
_pthread_body 0x00007fff652a5661
_pthread_start 0x00007fff652a550d
thread_start 0x00007fff652a4bf9

The offending code is the following:

for (auto itr = digits_.rbegin(); itr != digits_.rend(); ++itr) {
    output = output.MultiplyAndAdd(radix_, *itr);
  }

This could be replaced with a more efficient algorithm which runs in O(n log n)