* Re: [Bitcoin-development] Speeding up "getbalance <account>" calls
2011-06-24 5:30 ` John Smith
@ 2011-07-03 16:29 ` Jan Vornberger
[not found] ` <20431_1309711872_p63GpBTM023936_48918.130.226.56.2.1309710545.squirrel@webmail.uni-osnabrueck.de>
1 sibling, 0 replies; 4+ messages in thread
From: Jan Vornberger @ 2011-07-03 16:29 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]
Hey!
John Smith wrote:
> I think the easiest way to speed this up would be to scan the wallet every
> time a block comes in or something else changes in the block chain (or, if
> you prefer, some pre-set interval of N minutes). Then go over the entire
> wallet and the accumulate balances for all accounts. This could be done in
> amortized linear time using a hash_map.
That was a good suggestion - thanks! I implemented it along these lines
and now the Instawallet server can breath again. Well, more or less at
least, as now "sendfrom" starts acting up and I have to look into that
next.
Here is a branch with the code for the cache:
https://github.com/javgh/bitcoin/tree/balancecache . It's currently based
on a somewhat old version of the codebase as I'm running with a number of
other modifications. So it won't easily apply to something newer. I hope
to be able to switch to a recent version at some point (mostly hoping for
some improvements in the fee handling area before I do that) and then I
can hopefully provide a cleaner version of this patch. For now, I just
document it here for anyone who might need this as well and can piece it
together themselves (I attached a patch file).
Basically I create a list of all account balances every time a new a new
block comes in or a transaction that affects my wallet appears. The list
is stored in a "map" right now. This seems fast enough for me. I didn't
use a hash map for now, because I'm fairly new to C++ and was a little
confused on what to use (is there a "standard" hash map to use in the STL?
or do people use boost or what?). But my VPS is low on memory anyway, so I
guess that's kind of a justification as well to go for a tree-based
implementation of map.
Cheers!
Jan
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: balancecache.patch --]
[-- Type: text/x-patch; name="balancecache.patch", Size: 8184 bytes --]
diff --git a/init.cpp b/init.cpp
index bac4b28..948c11e 100644
--- a/init.cpp
+++ b/init.cpp
@@ -503,6 +503,9 @@ bool AppInit2(int argc, char* argv[])
RandAddSeedPerfmon();
+ // build initial balance cache
+ CreateAccountBalanceCache();
+
if (!CreateThread(StartNode, NULL))
wxMessageBox("Error: CreateThread(StartNode) failed", "Bitcoin");
diff --git a/main.cpp b/main.cpp
index cebe97b..3e66bb9 100644
--- a/main.cpp
+++ b/main.cpp
@@ -52,6 +52,9 @@ CCriticalSection cs_mapRequestCount;
map<string, string> mapAddressBook;
CCriticalSection cs_mapAddressBook;
+map<pair<string, int>, int64> mapAccountBalanceCache;
+CCriticalSection cs_mapAccountBalanceCache;
+
vector<unsigned char> vchDefaultKey;
CCriticalSection cs_mapMonitored;
@@ -109,6 +112,55 @@ vector<unsigned char> GenerateNewKey()
}
+//////////////////////////////////////////////////////////////////////////////
+//
+// mapAccountBalanceCache
+//
+
+void CreateAccountBalanceCache()
+{
+ CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+ {
+ printf("Rebuilding balance cache...\n");
+
+ CWalletDB walletdb;
+ mapAccountBalanceCache.clear();
+
+ CRITICAL_BLOCK(cs_mapAddressBook)
+ {
+ // find all accounts
+ foreach(const PAIRTYPE(string, string)& addressBookItem, mapAddressBook)
+ {
+ if (addressBookItem.second.empty())
+ continue;
+
+ for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+ {
+ mapAccountBalanceCache[make_pair(addressBookItem.second, nMinDepth)] = 0;
+ }
+ }
+
+ CRITICAL_BLOCK(cs_mapWallet)
+ {
+ // Tally wallet transactions
+ for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
+ {
+ const CWalletTx& wtx = (*it).second;
+ if (!wtx.IsFinal())
+ continue;
+
+ wtx.UpdateAccountBalanceCache();
+ }
+
+ // Tally internal accounting entries
+ foreach(const PAIRTYPE(const PAIRTYPE (string, int)&, int64)& item, mapAccountBalanceCache)
+ {
+ mapAccountBalanceCache[item.first] += walletdb.GetAccountCreditDebit(item.first.first);
+ }
+ }
+ }
+ }
+}
//////////////////////////////////////////////////////////////////////////////
@@ -179,6 +231,9 @@ bool AddToWallet(const CWalletTx& wtxIn)
// Notify any urls monitoring
if (!setMonitorTx.empty())
monitorTx(wtx);
+
+ // Rebuild balance cache
+ CreateAccountBalanceCache();
}
// Refresh UI
@@ -519,7 +574,38 @@ void CWalletTx::GetAccountAmounts(const string& strAccount, int64& nGenerated, i
}
}
+void CWalletTx::UpdateAccountBalanceCache() const
+{
+ int64 allGeneratedImmature, allGeneratedMature, allFee;
+ allGeneratedImmature = allGeneratedMature = allFee = 0;
+ string strSentAccount;
+ list<pair<string, int64> > listReceived;
+ list<pair<string, int64> > listSent;
+ GetAmounts(allGeneratedImmature, allGeneratedMature, listReceived, listSent, allFee, strSentAccount);
+ for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+ {
+ // see if an account was affected by sending money somewhere
+ if (mapAccountBalanceCache.count(make_pair(strSentAccount, nMinDepth)))
+ {
+ foreach(const PAIRTYPE(string,int64)& s, listSent)
+ mapAccountBalanceCache[make_pair(strSentAccount, nMinDepth)] -= s.second;
+ mapAccountBalanceCache[make_pair(strSentAccount, nMinDepth)] -= allFee;
+ }
+
+ // go through listReceived and update accounts that are affected
+ if (GetDepthInMainChain() >= nMinDepth)
+ {
+ foreach(const PAIRTYPE(string,int64)& r, listReceived)
+ {
+ if (mapAddressBook.count(r.first) && mapAccountBalanceCache.count(make_pair(mapAddressBook[r.first], nMinDepth)))
+ {
+ mapAccountBalanceCache[make_pair(mapAddressBook[r.first], nMinDepth)] += r.second;
+ }
+ }
+ }
+ }
+}
int CMerkleTx::SetMerkleBranch(const CBlock* pblock)
{
@@ -2769,6 +2855,9 @@ bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
if (ProcessBlock(pfrom, &block))
mapAlreadyAskedFor.erase(inv);
+
+ // Rebuild balance cache
+ CreateAccountBalanceCache();
}
diff --git a/main.h b/main.h
index 8f9345e..6dfab90 100644
--- a/main.h
+++ b/main.h
@@ -27,7 +27,7 @@ static const int fHaveUPnP = true;
#else
static const int fHaveUPnP = false;
#endif
-
+static const int ACCOUNT_BALANCE_CACHE_DEPTH = 2;
@@ -56,6 +56,9 @@ extern CCriticalSection cs_mapMonitored;
extern std::set<std::string> setMonitorTx; // set of urls listening for new transactions
extern std::set<std::string> setMonitorBlocks; // set of urls listening for new blocks
+extern map<pair<string, int>, int64> mapAccountBalanceCache;
+extern CCriticalSection cs_mapAccountBalanceCache;
+
// Settings
extern int fGenerateBitcoins;
extern int64 nTransactionFee;
@@ -103,6 +106,7 @@ void BitcoinMiner();
bool CheckProofOfWork(uint256 hash, unsigned int nBits);
bool IsInitialBlockDownload();
string GetWarnings(string strFor);
+void CreateAccountBalanceCache();
@@ -1006,6 +1010,8 @@ public:
void GetAccountAmounts(const string& strAccount, int64& nGenerated, int64& nReceived,
int64& nSent, int64& nFee) const;
+ void UpdateAccountBalanceCache() const;
+
bool IsFromMe() const
{
return (GetDebit() > 0);
diff --git a/rpc.cpp b/rpc.cpp
index 3807aa7..bd89fc9 100644
--- a/rpc.cpp
+++ b/rpc.cpp
@@ -358,6 +358,13 @@ string GetAccountAddress(string strAccount, bool bForceNew=false)
string strAddress = PubKeyToAddress(account.vchPubKey);
SetAddressBookName(strAddress, strAccount);
walletdb.WriteAccount(strAccount, account);
+
+ // Update balance cache
+ CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+ {
+ for (int nMinDepth = 0; nMinDepth <= ACCOUNT_BALANCE_CACHE_DEPTH; nMinDepth++)
+ mapAccountBalanceCache[make_pair(strAccount, nMinDepth)] = 0;
+ }
}
walletdb.TxnCommit();
@@ -603,9 +610,17 @@ Value getreceivedbyaccount(const Array& params, bool fHelp)
return (double)nAmount / (double)COIN;
}
-
-int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinDepth)
+int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinDepth, bool fUseCache = true)
{
+ // check the cache first
+ CRITICAL_BLOCK(cs_mapAccountBalanceCache)
+ {
+ map<pair<string, int>, int64>::iterator it = mapAccountBalanceCache.find(make_pair(strAccount, nMinDepth));
+ if (fUseCache && it != mapAccountBalanceCache.end())
+ return (*it).second;
+ }
+
+ // in case of cache miss: calculate from scratch
int64 nBalance = 0;
CRITICAL_BLOCK(cs_mapWallet)
{
@@ -631,13 +646,12 @@ int64 GetAccountBalance(CWalletDB& walletdb, const string& strAccount, int nMinD
return nBalance;
}
-int64 GetAccountBalance(const string& strAccount, int nMinDepth)
+int64 GetAccountBalance(const string& strAccount, int nMinDepth, bool fUseCache = true)
{
CWalletDB walletdb;
- return GetAccountBalance(walletdb, strAccount, nMinDepth);
+ return GetAccountBalance(walletdb, strAccount, nMinDepth, fUseCache);
}
-
Value getbalance(const Array& params, bool fHelp)
{
if (fHelp || params.size() < 0 || params.size() > 2)
@@ -683,7 +697,7 @@ Value getbalance(const Array& params, bool fHelp)
string strAccount = AccountFromValue(params[0]);
- int64 nBalance = GetAccountBalance(strAccount, nMinDepth);
+ int64 nBalance= GetAccountBalance(strAccount, nMinDepth);
return ValueFromAmount(nBalance);
}
^ permalink raw reply [flat|nested] 4+ messages in thread