[{"id":3848,"web_url":"https://patchwork.libcamera.org/comment/3848/","msgid":"<20200226144422.6tmc5o72htvqm5i2@uno.localdomain>","date":"2020-02-26T14:44:22","subject":"Re: [libcamera-devel] [PATCH v2 4/4] libcamera: V4L2BufferCache:\n\tImprove cache eviction strategy","submitter":{"id":3,"url":"https://patchwork.libcamera.org/api/people/3/","name":"Jacopo Mondi","email":"jacopo@jmondi.org"},"content":"Hi Niklas,\n\nOn Mon, Feb 24, 2020 at 08:36:01PM +0100, Niklas Söderlund wrote:\n> The strategy used to find a free cache entry in the first implementation\n> was not the smartest, it picked the first free entry. This lead to\n> unwanted performance issues as they cache was not used as good as it\n> could for imported buffers.\n>\n> Improve this by adding a last usage timestamp to the cache entries and\n> change the eviction strategy to use the oldest free entry instead of the\n> first one it finds.\n>\n> Signed-off-by: Niklas Söderlund \n> Reviewed-by: Naushir Patuck \n> ---\n> src/libcamera/include/v4l2_videodevice.h | 1 +\n> src/libcamera/v4l2_videodevice.cpp | 9 ++++++---\n> 2 files changed, 7 insertions(+), 3 deletions(-)\n>\n> diff --git a/src/libcamera/include/v4l2_videodevice.h b/src/libcamera/include/v4l2_videodevice.h\n> index fcf072641420dacf..f04feed87b24f28f 100644\n> --- a/src/libcamera/include/v4l2_videodevice.h\n> +++ b/src/libcamera/include/v4l2_videodevice.h\n> @@ -125,6 +125,7 @@ private:\n> \t\tbool operator==(const FrameBuffer &buffer);\n>\n> \t\tbool free;\n> +\t\tutils::time_point lastUsed;\n>\n> \tprivate:\n> \t\tstruct Plane {\n> diff --git a/src/libcamera/v4l2_videodevice.cpp b/src/libcamera/v4l2_videodevice.cpp\n> index 99470ce11421c77c..9a4d2479b20f5e27 100644\n> --- a/src/libcamera/v4l2_videodevice.cpp\n> +++ b/src/libcamera/v4l2_videodevice.cpp\n> @@ -205,6 +205,7 @@ int V4L2BufferCache::get(const FrameBuffer &buffer)\n> {\n> \tbool hit = false;\n> \tint use = -1;\n> +\tutils::time_point oldest = utils::clock::now();\n>\n> \tfor (unsigned int index = 0; index < cache_.size(); index++) {\n> \t\tconst Entry &entry = cache_[index];\n> @@ -212,8 +213,10 @@ int V4L2BufferCache::get(const FrameBuffer &buffer)\n> \t\tif (!entry.free)\n> \t\t\tcontinue;\n>\n> -\t\tif (use < 0)\n> +\t\tif (cache_[index].lastUsed < oldest) {\n\nentry.lastUsed\n\n> \t\t\tuse = index;\n> +\t\t\toldest = cache_[index].lastUsed;\n> +\t\t}\n\nCould you move this -after- having verified we didn't hit an hot entry ?\n\nIt seems more natural to\n\n for (entry: cache) {\n if (!entry.free)\n continue;\n\n if (entry == buffer) {\n hit = true;\n break;\n }\n\n if (entry.lastUsed < oldest)\n oldest = entry;\n }\n>\n> \t\t/* Try to find a cache hit by comparing the planes. */\n> \t\tif (cache_[index] == buffer) {\n\nYou could actually use entry here as well.\n\nMinors apart\nReviewed-by: Jacopo Mondi \n\nThanks\n j\n\n> @@ -245,12 +248,12 @@ void V4L2BufferCache::put(unsigned int index)\n> }\n>\n> V4L2BufferCache::Entry::Entry()\n> -\t: free(true)\n> +\t: free(true), lastUsed(utils::clock::now())\n> {\n> }\n>\n> V4L2BufferCache::Entry::Entry(bool free, const FrameBuffer &buffer)\n> -\t: free(free)\n> +\t: free(free), lastUsed(utils::clock::now())\n> {\n> \tfor (const FrameBuffer::Plane &plane : buffer.planes())\n> \t\tplanes_.emplace_back(plane);\n> --\n> 2.25.0\n>\n> _______________________________________________\n> libcamera-devel mailing list\n> libcamera-devel@lists.libcamera.org\n> https://lists.libcamera.org/listinfo/libcamera-devel","headers":{"Return-Path":"","Received":["from relay11.mail.gandi.net (relay11.mail.gandi.net\n\t[217.70.178.231])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 84E936042D\n\tfor ;\n\tWed, 26 Feb 2020 15:41:44 +0100 (CET)","from uno.localdomain (93-34-114-233.ip49.fastwebnet.it\n\t[93.34.114.233]) (Authenticated sender: jacopo@jmondi.org)\n\tby relay11.mail.gandi.net (Postfix) with ESMTPSA id F0D2710000F;\n\tWed, 26 Feb 2020 14:41:34 +0000 (UTC)"],"Date":"Wed, 26 Feb 2020 15:44:22 +0100","From":"Jacopo Mondi ","To":"Niklas =?utf-8?q?S=C3=B6derlund?= ","Cc":"libcamera-devel@lists.libcamera.org","Message-ID":"<20200226144422.6tmc5o72htvqm5i2@uno.localdomain>","References":"<20200224193601.1040770-1-niklas.soderlund@ragnatech.se>\n\t<20200224193601.1040770-5-niklas.soderlund@ragnatech.se>","MIME-Version":"1.0","Content-Type":"multipart/signed; micalg=pgp-sha256;\n\tprotocol=\"application/pgp-signature\"; boundary=\"3zvz5l632tufea7q\"","Content-Disposition":"inline","In-Reply-To":"<20200224193601.1040770-5-niklas.soderlund@ragnatech.se>","Subject":"Re: [libcamera-devel] [PATCH v2 4/4] libcamera: V4L2BufferCache:\n\tImprove cache eviction strategy","X-BeenThere":"libcamera-devel@lists.libcamera.org","X-Mailman-Version":"2.1.29","Precedence":"list","List-Id":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","X-List-Received-Date":"Wed, 26 Feb 2020 14:41:44 -0000"}},{"id":3889,"web_url":"https://patchwork.libcamera.org/comment/3889/","msgid":"<20200229162540.GF18738@pendragon.ideasonboard.com>","date":"2020-02-29T16:25:40","subject":"Re: [libcamera-devel] [PATCH v2 4/4] libcamera: V4L2BufferCache:\n\tImprove cache eviction strategy","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"Hi Niklas,\n\nThank you for the patch.\n\nOn Wed, Feb 26, 2020 at 03:44:22PM +0100, Jacopo Mondi wrote:\n> On Mon, Feb 24, 2020 at 08:36:01PM +0100, Niklas Söderlund wrote:\n> > The strategy used to find a free cache entry in the first implementation\n> > was not the smartest, it picked the first free entry. This lead to\n> > unwanted performance issues as they cache was not used as good as it\n\ns/they cache/the cache/\n\n> > could for imported buffers.\n> >\n> > Improve this by adding a last usage timestamp to the cache entries and\n> > change the eviction strategy to use the oldest free entry instead of the\n> > first one it finds.\n> >\n> > Signed-off-by: Niklas Söderlund \n> > Reviewed-by: Naushir Patuck \n> > ---\n> > src/libcamera/include/v4l2_videodevice.h | 1 +\n> > src/libcamera/v4l2_videodevice.cpp | 9 ++++++---\n> > 2 files changed, 7 insertions(+), 3 deletions(-)\n> >\n> > diff --git a/src/libcamera/include/v4l2_videodevice.h b/src/libcamera/include/v4l2_videodevice.h\n> > index fcf072641420dacf..f04feed87b24f28f 100644\n> > --- a/src/libcamera/include/v4l2_videodevice.h\n> > +++ b/src/libcamera/include/v4l2_videodevice.h\n> > @@ -125,6 +125,7 @@ private:\n> > \t\tbool operator==(const FrameBuffer &buffer);\n> >\n> > \t\tbool free;\n> > +\t\tutils::time_point lastUsed;\n\nWould it be more efficient to use a sequence number, to avoid getting\nthe system clock all the time ? This would require adding a private\nstd::atomic_uint32_t (or a 64-bit type ?) in the V4L2BufferCache class,\ncalling .fetch_add() on it in V4L2BufferCache::get(), and passing the\nvalue to the Entry() constructor. Entry would have an uint32_t lastUsed\nfield, with the default Entry() constructor setting it to 0.\n\nWith that I'm OK with the implementation.\n\n> >\n> > \tprivate:\n> > \t\tstruct Plane {\n> > diff --git a/src/libcamera/v4l2_videodevice.cpp b/src/libcamera/v4l2_videodevice.cpp\n> > index 99470ce11421c77c..9a4d2479b20f5e27 100644\n> > --- a/src/libcamera/v4l2_videodevice.cpp\n> > +++ b/src/libcamera/v4l2_videodevice.cpp\n> > @@ -205,6 +205,7 @@ int V4L2BufferCache::get(const FrameBuffer &buffer)\n> > {\n> > \tbool hit = false;\n> > \tint use = -1;\n> > +\tutils::time_point oldest = utils::clock::now();\n\nThis would become\n\n\tuint32_t oldest = UINT32_MAX;\n\n> >\n> > \tfor (unsigned int index = 0; index < cache_.size(); index++) {\n> > \t\tconst Entry &entry = cache_[index];\n> > @@ -212,8 +213,10 @@ int V4L2BufferCache::get(const FrameBuffer &buffer)\n> > \t\tif (!entry.free)\n> > \t\t\tcontinue;\n> >\n> > -\t\tif (use < 0)\n> > +\t\tif (cache_[index].lastUsed < oldest) {\n> \n> entry.lastUsed\n> \n> > \t\t\tuse = index;\n> > +\t\t\toldest = cache_[index].lastUsed;\n> > +\t\t}\n> \n> Could you move this -after- having verified we didn't hit an hot entry ?\n> \n> It seems more natural to\n> \n> for (entry: cache) {\n> if (!entry.free)\n> continue;\n> \n> if (entry == buffer) {\n> hit = true;\n> break;\n> }\n> \n> if (entry.lastUsed < oldest)\n> oldest = entry;\n\nMissing\n\n\t\t\tuse = index;\n\nI think\n\n> }\n> >\n> > \t\t/* Try to find a cache hit by comparing the planes. */\n> > \t\tif (cache_[index] == buffer) {\n> \n> You could actually use entry here as well.\n> \n> Minors apart\n> Reviewed-by: Jacopo Mondi \n> \n> > @@ -245,12 +248,12 @@ void V4L2BufferCache::put(unsigned int index)\n> > }\n> >\n> > V4L2BufferCache::Entry::Entry()\n> > -\t: free(true)\n> > +\t: free(true), lastUsed(utils::clock::now())\n> > {\n> > }\n> >\n> > V4L2BufferCache::Entry::Entry(bool free, const FrameBuffer &buffer)\n> > -\t: free(free)\n> > +\t: free(free), lastUsed(utils::clock::now())\n> > {\n> > \tfor (const FrameBuffer::Plane &plane : buffer.planes())\n> > \t\tplanes_.emplace_back(plane);","headers":{"Return-Path":"","Received":["from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[IPv6:2001:4b98:dc2:55:216:3eff:fef7:d647])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 856C162689\n\tfor ;\n\tSat, 29 Feb 2020 17:26:04 +0100 (CET)","from pendragon.ideasonboard.com (81-175-216-236.bb.dnainternet.fi\n\t[81.175.216.236])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id EE1E233E;\n\tSat, 29 Feb 2020 17:26:03 +0100 (CET)"],"DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1582993564;\n\tbh=1dE28PjQEE5BZA/1Q/kP5boJUC5SK5OegNV9kqvG2xs=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=W6WAO6cUf1aUw4vRFggg/cKNuDzcHKWNmQY4S5VjmQWULSFaEolriq9bgycCTRxgu\n\tFLwcfgKmU39rOvFfn586YMhtWtOCWe53DEgeeXPWOYTjxPHNGYvR8XyquaYn8Mry1U\n\tnKaKK3r4Lc4hPWb+BTO0BLZWCWdlICen8/p2J4JM=","Date":"Sat, 29 Feb 2020 18:25:40 +0200","From":"Laurent Pinchart ","To":"Jacopo Mondi ","Cc":"Niklas =?utf-8?q?S=C3=B6derlund?= ,\n\tlibcamera-devel@lists.libcamera.org","Message-ID":"<20200229162540.GF18738@pendragon.ideasonboard.com>","References":"<20200224193601.1040770-1-niklas.soderlund@ragnatech.se>\n\t<20200224193601.1040770-5-niklas.soderlund@ragnatech.se>\n\t<20200226144422.6tmc5o72htvqm5i2@uno.localdomain>","MIME-Version":"1.0","Content-Type":"text/plain; charset=utf-8","Content-Disposition":"inline","Content-Transfer-Encoding":"8bit","In-Reply-To":"<20200226144422.6tmc5o72htvqm5i2@uno.localdomain>","User-Agent":"Mutt/1.10.1 (2018-07-13)","Subject":"Re: [libcamera-devel] [PATCH v2 4/4] libcamera: V4L2BufferCache:\n\tImprove cache eviction strategy","X-BeenThere":"libcamera-devel@lists.libcamera.org","X-Mailman-Version":"2.1.29","Precedence":"list","List-Id":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","X-List-Received-Date":"Sat, 29 Feb 2020 16:26:04 -0000"}}]