Page MenuHomePhabricator
Create Task
Maniphest T77

Consider removing prevector and switching back to good 'ol vector (with possible .reserve calls)
Open, WishlistPublic
Actions

Description

Hi guys,

I did a little investigation and I am not entirely sure *why* bitcoin uses prevector. In my tests the 'gain' from prevector is highly platform-dependent, and was never more than 10%. With some newer libstdc++'s, prevector was actually as much as 50% *slower* in some tests.

Here is a small test program that tests prevector vs regular vector-with-reserve: https://github.com/cculianu/prevector_bench

In my opinion prevector just adds technical debt (need to constantly maintain it if standard vector changes, etc) without any huge benefit that I can ascertain.

I did a little digging and I can't find out the rationale core used to add it in the first place.

Anyway -- if you have time check out my little prevector_bench utility and let me know what you think and/or how it performs on your platform/c++ lib version.

Event Timeline

CCulianu created this task.Jul 27 2017, 11:55
CCulianu added a comment.Jul 27 2017, 15:26

Note, I went ahead and recompiled bitcoin-abc (current master as of the time of this writing) both with and without prevector.

My 'NoPrevector' version basically swaps out prevector with a stub class that inherits std::vector and does a reserve() on the N (size) template parameter.

Anyway.. after many runs of test_bitcoin and bench_bitcoin, basically the performance is more or less the same, to within +/- 1%. Here is a sample run:

Running test_bitcoin 5 times for both NoPrevector and Prevector versions...
NoPrevector 1
Time=39.90
Prevector 1
Time=39.59
NoPrevector 2
Time=40.47
Prevector 2
Time=39.26
NoPrevector 3
Time=40.60
Prevector 3
Time=39.84
NoPrevector 4
Time=39.71
Prevector 4
Time=39.71
NoPrevector 5
Time=40.48
Prevector 5
Time=39.42
test_bitcoin after 5 iterations: NoPrevector=201.16 Prevector=197.82  Speedup=1.016x
Running bench_bitcoin 5 times for both NoPrevector and Prevector versions...
NoPrevector 1
Time=21.52
Prevector 1
Time=21.78
NoPrevector 2
Time=21.39
Prevector 2
Time=21.54
NoPrevector 3
Time=21.67
Prevector 3
Time=21.67
NoPrevector 4
Time=21.52
Prevector 4
Time=21.84
NoPrevector 5
Time=21.76
Prevector 5
Time=21.95
bench_bitcoin after 5 iterations: NoPrevector=107.86 Prevector=108.78  Speedup=.991x

So this begs the question more -- why do we have prevector? Seems just like a risky little "premature optimization" that can someday be the root of evil..

I'd like very much to excise it from the sources. Mu ha ha. :)

freetrader added a comment.Aug 9 2017, 10:09

Something relevant to this matter:

https://github.com/bitcoin/bitcoin/pull/11011/files

CCulianu added a project: Restricted Project.Aug 9 2017, 20:40
schancel removed CCulianu as the assignee of this task.Sep 28 2018, 21:25
schancel added a project: Bootcamp.
schancel removed subscribers: freetrader, CCulianu.
Unknown Object (User) added a subscriber: Unknown Object (User).Jun 29 2020, 07:18
This comment was removed by deadalnix.