Skip to content

Improve EncodeBase58 performance #7656

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.

Sign up for GitHub

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

Merged
laanwj merged 1 commit into from
Mar 21, 2016
Merged

Improve EncodeBase58 performance #7656

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
11 changes: 8 additions & 3 deletions src/base58.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -68,26 +68,31 @@ std::string EncodeBase58(const unsigned char* pbegin, const unsigned char* pend)
{
// Skip & count leading zeroes.
int zeroes = 0;
int length = 0;
while (pbegin != pend && *pbegin == 0) {
pbegin++;
zeroes++;
}
// Allocate enough space in big-endian base58 representation.
std::vector<unsigned char> b58((pend - pbegin) * 138 / 100 + 1); // log(256) / log(58), rounded up.
int size = (pend - pbegin) * 138 / 100 + 1; // log(256) / log(58), rounded up.
std::vector<unsigned char> b58(size);
// Process the bytes.
while (pbegin != pend) {
int carry = *pbegin;
int i = 0;
// Apply "b58 = b58 * 256 + ch".
for (std::vector<unsigned char>::reverse_iterator it = b58.rbegin(); it != b58.rend(); it++) {
for (std::vector<unsigned char>::reverse_iterator it = b58.rbegin(); (carry != 0 || i < length) && (it != b58.rend()); it++, i++) {
Copy link
Contributor

@fanatid fanatid Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Wouldn't ++it faster than it++?

Copy link
Member

@maflcko maflcko Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Presumably, yes: http://stackoverflow.com/a/35085/2084795

Copy link
Member

@laanwj laanwj Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

for iterators that may well be the case (prefix increment saves a copy)

Copy link
Contributor

@jtimon jtimon Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This should depend on the compiler and target machine anyway, but it is my understanding that in x86 there are separated instructions with different performance (how big is the difference I have no idea). I also suspect that many compilers are smart enough to do this for you.
So if it may not do anything but if it may do something good, why not?
Of course this is not to say we should do it everywhere. But in new code, why not? It may be useful for some platforms. The cons from stackoverflow seem very week, but I'm very curious if anybody else has some other more solid concerns or benchmarks showing this is not really something to think much about (or just data showing that, yes, compilers are currently smart for this too). This is a recurring discussion that I would like to stop thinking about one way or the other.

Copy link
Member

@laanwj laanwj Mar 18, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This should depend on the compiler and target machine anyway, but it is my understanding that in x86 there are separated instructions with different performance

For integers the compiler is certainly smart enough that there is no difference between prefix and postfix ++, if bare (the result is not actually used).

But this doesn't have much to do with the instructions, just with language design. Iterators are objects. The definition of prefix and postfix ++ respectively is, when overloading them:

Point& operator++();       // Prefix increment operator.
Point operator++(int);     // Postfix increment operator.

So: postfix operation returns a copy (the old value), whereas prefix increments in place and returns a reference (to self). This means prefix can, in principle, be implemented more efficiently.

Copy link
Member

@luke-jr luke-jr Mar 20, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe change it++ to ++it while we're optimising... (it++ creates an unnecessary copy of the iterator)

carry += 256 * (*it);
*it = carry % 58;
carry /= 58;
}

assert(carry == 0);
Copy link
Member

@luke-jr luke-jr Mar 20, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This could be transformed into an assert(it != b58.rend()); within the loop.

length = i;
Copy link
Contributor

@jtimon jtimon Mar 16, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do you really need both i and length?
It seems you could simply ++length; here. I see your i < length condition, but I don't see how can it possibly be ever true.

Copy link
Contributor

@fanatid fanatid Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It isn't simply ++length, it can be length += 0|1|2, but there is possible to remove i:
length = it - b58.begin()

Copy link
Contributor

@jtimon jtimon Mar 17, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

mhmm, I need to read this more deeply for an utACK, I think. I retire my utACK but maintain the concept ACK.

pbegin++;
}
// Skip leading zeroes in base58 result.
std::vector<unsigned char>::iterator it = b58.begin();
std::vector<unsigned char>::iterator it = b58.begin() + (size - length);
while (it != b58.end() && *it == 0)
it++;
// Translate the result into a string.
Expand Down