Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve lower_bound(min_price) performance #1671

Open
1 of 17 tasks
abitmore opened this issue Mar 23, 2019 · 1 comment
Open
1 of 17 tasks

Improve lower_bound(min_price) performance #1671

abitmore opened this issue Mar 23, 2019 · 1 comment
Labels
6 Performance Impacts flag identifying system/user efficiency, performance, etc. performance

Comments

@abitmore
Copy link
Member

abitmore commented Mar 23, 2019

User Story
When calling something like an_index::lower_bound(price.min(a,b)) as well as upper_bound(max_price), step into lower_bound(), when the pointer is on a record with price(a,b), 128-bit computations will occur, see

const auto amult = uint128_t( b.quote.amount.value ) * a.base.amount.value;
const auto bmult = uint128_t( a.quote.amount.value ) * b.base.amount.value;

IMHO the 128-bit computation is unnecessary in this case since operator<() will always return true (or false when in another direction). If we can find a way to avoid the computation without much overhead, we may be able to get better performance. Need benchmark.

Related to #1094. Part of #982.

Impacts
Describe which portion(s) of BitShares Core may be impacted by your request. Please tick at least one box.

  • API (the application programming interface)
  • Build (the build process or something prior to compiled code)
  • CLI (the command line wallet)
  • Deployment (the deployment process after building such as Docker, Travis, etc.)
  • DEX (the Decentralized EXchange, market engine, etc.)
  • P2P (the peer-to-peer network for transaction/block propagation)
  • Performance (system or user efficiency, etc.)
  • Protocol (the blockchain logic, consensus, validation, etc.)
  • Security (the security of system or user data, etc.)
  • UX (the User Experience)
  • Other (please add below)

Additional Context (optional)
Add any other context about your request here.

CORE TEAM TASK LIST

  • Evaluate / Prioritize Feature Request
  • Refine User Stories / Requirements
  • Define Test Cases
  • Design / Develop Solution
  • Perform QA/Testing
  • Update Documentation
@abitmore abitmore added performance 6 Performance Impacts flag identifying system/user efficiency, performance, etc. labels Mar 23, 2019
@abitmore abitmore added this to the Future Feature Release milestone Mar 23, 2019
@pmconrad
Copy link
Contributor

Assuming the index is organized as a tree, any lookup (or insert) operation will have to traverse the tree and make a comparison at each node. In the case of lookup by price, a large fraction of these comparisons will be decided only by looking at the asset IDs, which is cheap. Comparisons on the numeric parts are unavoidable in the general case.

In the specific case of min/max lookups, comparisons could be avoided if all elements for a particular asset pair were stored in an index of their own. In that case, the min/max lookup would be equivalent to begin/end of the pair-specific index, which should work without comparisons.
The question is if this would pay off. There certainly is some potential, seeing that mix/max lookups are used quite often by the market engine.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
6 Performance Impacts flag identifying system/user efficiency, performance, etc. performance
Projects
None yet
Development

No branches or pull requests

2 participants