From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47739) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZbIm4-0007nm-DD for qemu-devel@nongnu.org; Sun, 13 Sep 2015 21:41:41 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZbIm0-0001o3-AM for qemu-devel@nongnu.org; Sun, 13 Sep 2015 21:41:40 -0400 Date: Mon, 14 Sep 2015 11:26:42 +1000 From: David Gibson Message-ID: <20150914012642.GA2547@voom.fritz.box> References: <1441866505-10842-1-git-send-email-david@gibson.dropbear.id.au> <55F2CC7F.1090609@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="sm4nu43k4a2Rpi4c" Content-Disposition: inline In-Reply-To: <55F2CC7F.1090609@redhat.com> Subject: Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2) List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Paolo Bonzini Cc: aik@ozlabs.ru, qemu-devel@nongnu.org, qemu-ppc@nongnu.org, agraf@suse.de, bharata@linux.vnet.ibm.com --sm4nu43k4a2Rpi4c Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Sep 11, 2015 at 02:43:43PM +0200, Paolo Bonzini wrote: >=20 >=20 > On 10/09/2015 08:28, David Gibson wrote: > > The dynamic reconfiguration (hotplug) code for the pseries machine type > > uses a "DR connector" QOM object for each resource it will be possible > > to hotplug. Each of these is added to its owner using > > object_property_add_child(owner, "dr-connector[*], ...); > >=20 > > This works ok for most cases, but gets ugly when allowing large amounts= of > > hotplugged RAM. For RAM, there's a DR connector object for every 256MB= of > > potential memory. So if maxmem=3D2T, for example, there are >250,000 o= bjects > > under the same parent. >=20 > That must consume quite some memory... I would guess 1K per object. So, Bharata was right, it's only ~32k objects even for maxmem=3D4T. I'm not quite sure how I messed up my arithmetic there. But still, yeah, it's a lot of objects :/. Medium term I think we should avoid creating so many objects for the connectors. I'm thinking a "connector array" object that handles a whole range of connector indices them with a single QOM object should be possible. > > The QOM interfaces aren't really designed for this. In particular > > object_property_add() has O(n^2) time complexity (in the number of exis= ting > > children) for the [*] case. First it has a linear search through array > > indices to find a free slot, each of which is attempted to a recursive = call > > to object_property_add() with a specific [N]. Those calls are O(n) bec= ause > > there's a linear search through all properties to check for duplicates. > >=20 > > For the specific case of DR connectors, we already have a sufficiently > > unique index, so we don't need to use the [*] special behaviour. That = lets > > us reduce the total time for creating the DR objects from O(n^3) to O(n= ^2). > >=20 > > O(n^2) is still kind of crappy, but it's enough to reduce the startup t= ime > > of qemu with maxmem=3D2T from ~20 minutes to ~4 seconds. >=20 > Thanks, I agree that even O(n^2) is crappy. We need to add a hash table > for properties, so that [*] is O(n^2) and the optimized case is > O(n). Right, so I had the impression that QOM isn't really built for handling thousands of objects under one parent. I don't have a wide enough view to know if that's a reasonable goal for it ever to handle well. Using a hash table at every node might be pretty expensive in memory for nodes with only a handful of children. --=20 David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson --sm4nu43k4a2Rpi4c Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJV9iJSAAoJEGw4ysog2bOSe0EQAJ0GEHkhOfB/t1+Nxci7I7bI HgYtL89rCCio5nq20drqOS83upE8dIahlKm3Na7MYZ5ClZ5sXoOTGTWBEbBz+Cnl mAauS07O3SLbDk/NIXisSiBzeC0bz1kjlT0Q6tgHbADwLNtNTkEHpOvzYNCbaXkt JmZ6z5tOlzUi/wLYR9KE7WOcM+v+X+5KiPfHQuupOqoJTaWqOVpY/xfRY1mMz0By TGKodwghZD3WI75cU1hhKSYwiE/KfGXGulSXOR9x1hDxL19cME9AJ8jDkiDM087m Nd8/kXEhDpSHUKpYjm6UXLYg0FIO4Kf4/Y00jQ+V3vndLX1XoZK1h4loIvfMx15y nu450QU6CH8xgfeCue/WYlc9HXcJHvw0/Ks8KkmO6snhau6UnTeWUhYzqByEPdH1 SMiVFiz87aXchDNw8h/ZovHAHLgUJROcDw+SOdDJyA05Lj5YVcVrm3TfydtKj4H7 RBTP2rf/JhhAlZcqdNkXyYVZnFGW4+6DeefMWAjj9TrEVyRzeJzTzhL/w7ZD3HEi NGmLptEdpaZ4BhshgVu6ytw3D8/bG55O22rsMyV/7pWqyc4+M5CEreYEE37zJnli CTkHxH/pMi9BvBY5Gaju8sJqSxlYDj9aWClnSDKPenuinYWniSTLa+A8vq//vzE7 X0DsUWcJhMgWcH6+L4S6 =aRf2 -----END PGP SIGNATURE----- --sm4nu43k4a2Rpi4c--