Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1QdPsu-0002Zp-K2 for bitcoin-development@lists.sourceforge.net; Sun, 03 Jul 2011 16:51:04 +0000 X-ACL-Warn: Received: from vm120.rz.uni-osnabrueck.de ([131.173.17.202] helo=mail-in-4.serv.Uni-Osnabrueck.DE) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) id 1QdPss-0002cS-2H for bitcoin-development@lists.sourceforge.net; Sun, 03 Jul 2011 16:51:04 +0000 Received: from vm179.rz.Uni-Osnabrueck.DE (vm179.rz.uni-osnabrueck.de [131.173.16.37]) by mail-in-4.serv.Uni-Osnabrueck.DE (8.13.8/8.13.8) with ESMTP id p63GT5I1016816 for ; Sun, 3 Jul 2011 18:29:05 +0200 Received: by vm179.rz.Uni-Osnabrueck.DE (Postfix, from userid 48) id 966C85B7; Sun, 3 Jul 2011 18:29:05 +0200 (CEST) Received: from 130.226.56.2 (SquirrelMail authenticated user jan) by webmail.uni-osnabrueck.de with HTTP; Sun, 3 Jul 2011 18:29:05 +0200 (CEST) Message-ID: <48918.130.226.56.2.1309710545.squirrel@webmail.uni-osnabrueck.de> In-Reply-To: References: <20110623215143.GA3351@dax.lan.local> Date: Sun, 3 Jul 2011 18:29:05 +0200 (CEST) From: "Jan Vornberger" To: bitcoin-development@lists.sourceforge.net User-Agent: SquirrelMail/1.4.8-5.el5_4.10 MIME-Version: 1.0 Content-Type: multipart/mixed;boundary="----=_20110703182905_83034" X-Priority: 3 (Normal) Importance: Normal X-PMX-Version: 5.5.9.395186, Antispam-Engine: 2.7.2.376379, Antispam-Data: 2011.7.3.161814 (Univ. Osnabrueck) X-PMX-Spam: Gauge=XI, Probability=11%, Report= PRIORITY_NO_NAME 0.716, MIME_TEXT_ONLY_MP_MIXED 0.05, BODYTEXTP_SIZE_3000_LESS 0, BODY_SIZE_10000_PLUS 0, WEBMAIL_SOURCE 0, WEBMAIL_USER_AGENT 0, __ANY_URI 0, __BOUNCE_CHALLENGE_SUBJ 0, __BOUNCE_NDR_SUBJ_EXEMPT 0, __CT 0, __CTYPE_HAS_BOUNDARY 0, __CTYPE_MULTIPART 0, __CTYPE_MULTIPART_MIXED 0, __HAS_MSGID 0, __HAS_X_PRIORITY 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __PHISH_SPEAR_HTTP_RECEIVED 0, __PHISH_SPEAR_STRUCTURE_1 0, __SANE_MSGID 0, __SUBJ_ALPHA_END 0, __TO_MALFORMED_2 0, __TO_NO_NAME 0, __URI_NO_MAILTO 0, __URI_NO_PATH 0, __URI_NO_WWW 0, __URI_NS , __USER_AGENT 0 X-PMX-Spam-Level: XI X-Spam-Score: 0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. X-Headers-End: 1QdPss-0002cS-2H Subject: Re: [Bitcoin-development] Speeding up "getbalance " calls X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 03 Jul 2011 16:51:04 -0000 ------=_20110703182905_83034 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit 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 ------=_20110703182905_83034 Content-Type: text/x-patch; name="balancecache.patch" Content-Transfer-Encoding: 8bit Content-Disposition: attachment; filename="balancecache.patch" 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 mapAddressBook; CCriticalSection cs_mapAddressBook; +map, int64> mapAccountBalanceCache; +CCriticalSection cs_mapAccountBalanceCache; + vector vchDefaultKey; CCriticalSection cs_mapMonitored; @@ -109,6 +112,55 @@ vector 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::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 > listReceived; + list > 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 setMonitorTx; // set of urls listening for new transactions extern std::set setMonitorBlocks; // set of urls listening for new blocks +extern map, 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, 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); } ------=_20110703182905_83034--