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

O(logN) complexity needed instead of O(N logN) when picking up multiple matching campaigns N>1 #76

Open
venediktov opened this issue Feb 8, 2018 · 1 comment

Comments

@venediktov
Copy link
Owner

venediktov commented Feb 8, 2018

Looks like last stage when we pick up campaigns from the cache the complexity is O(N LogN) , for every matched campaign id N we use LogN complexity lookup in the last cached table ~ O(N LogN) .
Matching 20-30 campaign per request is within our benchmark goals however going above this number degrades performance.

  • Use relational cache entries to solve the issue , we should avoid last stage campaign lookup , rather have pointers saved in the preceding matcher cache and use those pointers to retrieve campaigns directly instead of performing O(LogN) lookup.
@venediktov venediktov assigned mrbald, venediktov and abushev and unassigned venediktov Feb 8, 2018
@venediktov venediktov changed the title O(logN) complexity needed when picking up matching campaigns O(logN) complexity desired instead of O(N logN) when picking up multiple matching campaigns N>1 Mar 5, 2018
@venediktov venediktov changed the title O(logN) complexity desired instead of O(N logN) when picking up multiple matching campaigns N>1 O(logN) complexity needed instead of O(N logN) when picking up multiple matching campaigns N>1 Mar 5, 2018
@AKAnkshASing
Copy link

Hey, I am interested in resolving this issue

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants