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 <jan@uos.de>) 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 <bitcoin-development@lists.sourceforge.net>;
	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: <BANLkTi=eSgC0T_mKn660dZv1h+g-Z9TU+g@mail.gmail.com>
References: <20110623215143.GA3351@dax.lan.local>
	<BANLkTi=eSgC0T_mKn660dZv1h+g-Z9TU+g@mail.gmail.com>
Date: Sun, 3 Jul 2011 18:29:05 +0200 (CEST)
From: "Jan Vornberger" <jan@uos.de>
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 <account>" calls
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=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<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);
 }
------=_20110703182905_83034--