From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LUoyD-000171-95 for qemu-devel@nongnu.org; Wed, 04 Feb 2009 16:07:41 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LUoyB-00016W-Ki for qemu-devel@nongnu.org; Wed, 04 Feb 2009 16:07:40 -0500 Received: from [199.232.76.173] (port=43906 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LUoyB-00016S-Db for qemu-devel@nongnu.org; Wed, 04 Feb 2009 16:07:39 -0500 Received: from mx2.redhat.com ([66.187.237.31]:57983) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1LUoyA-0001aQ-Fo for qemu-devel@nongnu.org; Wed, 04 Feb 2009 16:07:39 -0500 Message-ID: <498A02B3.4070903@redhat.com> Date: Wed, 04 Feb 2009 23:03:47 +0200 From: Avi Kivity MIME-Version: 1.0 References: <1233750314-23301-1-git-send-email-avi@redhat.com> <1233750314-23301-2-git-send-email-avi@redhat.com> <4989EC29.9050705@us.ibm.com> <4989FACD.6090309@redhat.com> <4989FC3B.7010407@us.ibm.com> <4989FE92.5020400@redhat.com> <4989FF9B.4010809@us.ibm.com> In-Reply-To: <4989FF9B.4010809@us.ibm.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: [Qemu-devel] Re: [PATCH 1/4] Add a scatter-gather list type and accessors Reply-To: qemu-devel@nongnu.org List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Anthony Liguori Cc: qemu-devel@nongnu.org Anthony Liguori wrote: >> >> malloc() will never fail on Linux with overcommit enabled; since >> Linux is fairly useless without overcommit, it means you'll never see >> a failure. > > Sure it will. You just have to run out of VA space. > That's not recoverable, and is certainly a qemu bug if it happens. Especially on 47-bit hosts. >>>> I expect this to trigger rarely since the allocation hint should >>>> suffice nearly 100% of the time. But in case we miss, it's better >>>> to reallocate as little as possible. >>>> >>>> (what I really want is std::vector<>) >>> >>> Which I'm pretty sure has a linear growth strategy :-) >> >> Not in any of the implementations I'm familiar with. I believe >> std::vector<> is required to have amortized O(1) append operations. > > Linear growth doesn't imply element-by-element growth. You can have a > coefficient > 1. > If you have a coefficient, then it's exponential growth, even if it's less than two. If you have an addition, then it's linear growth, even if the addend is greater than one. size *= k -> exponential size += k -> linear -- I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.