[{"id":16368,"web_url":"https://patchwork.libcamera.org/comment/16368/","msgid":"","date":"2021-04-20T00:25:20","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"Hi Hiro,\n\nThank you for the patch.\n\nOn Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> The original updateControls() has the assumption that ctrls and\n> v4l2Ctrls lists in the same order. It is dependent on the caller\n> implementation though. This changes updateControls()\n> implementation so that it works without the assumption.\n> \n> Signed-off-by: Hirokazu Honda \n> ---\n> src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> 1 file changed, 13 insertions(+), 13 deletions(-)\n> \n> diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> index d4a9bb75..8fd79934 100644\n> --- a/src/libcamera/v4l2_device.cpp\n> +++ b/src/libcamera/v4l2_device.cpp\n> @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> \t\t\t\tconst struct v4l2_ext_control *v4l2Ctrls,\n> \t\t\t\tunsigned int count)\n> {\n> -\tunsigned int i = 0;\n> -\tfor (auto &ctrl : *ctrls) {\n> -\t\tif (i == count)\n> -\t\t\tbreak;\n> -\n> -\t\tconst struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> -\t\tunsigned int id = ctrl.first;\n> -\t\tControlValue &value = ctrl.second;\n> +\tfor (unsigned int i = 0; i < count; i++) {\n> +\t\tconst struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> +\t\tconst unsigned int id = v4l2Ctrl.id;\n> +\t\tif (!ctrls->contains(id)) {\n> +\t\t\tLOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> +\t\t\t\t\t << id;\n> +\t\t\treturn;\n> +\t\t}\n> \n> -\t\tconst auto iter = controls_.find(id);\n> -\t\tswitch (iter->first->type()) {\n> +\t\tControlValue value = ctrls->get(id);\n\nThis is less efficient, as the function now runs with O(n^2) complexity.\nGiven that updateControls() is private, why is requiring ctrls and\nv4l2Ctrls to have the same order a problem ? The requirement should be\ndocumented, but does it cause any issue ?\n\n> +\t\tswitch (value.type()) {\n> \t\tcase ControlTypeInteger64:\n> -\t\t\tvalue.set(v4l2Ctrl->value64);\n> +\t\t\tvalue.set(v4l2Ctrl.value64);\n> \t\t\tbreak;\n> \n> \t\tcase ControlTypeByte:\n> @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> \t\t\t * \\todo To be changed when support for string controls\n> \t\t\t * will be added.\n> \t\t\t */\n> -\t\t\tvalue.set(v4l2Ctrl->value);\n> +\t\t\tvalue.set(v4l2Ctrl.value);\n> \t\t\tbreak;\n> \t\t}\n> \n> -\t\ti++;\n> +\t\tctrls->set(id, value);\n> \t}\n> }\n>","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 218EABD814\n\tfor ;\n\tTue, 20 Apr 2021 00:25:27 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 576B168834;\n\tTue, 20 Apr 2021 02:25:26 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 5770B602CA\n\tfor ;\n\tTue, 20 Apr 2021 02:25:24 +0200 (CEST)","from pendragon.ideasonboard.com (62-78-145-57.bb.dnainternet.fi\n\t[62.78.145.57])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id C1692470;\n\tTue, 20 Apr 2021 02:25:23 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"bkTPFfoa\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618878323;\n\tbh=LvTaG97OH1eVY2eyWfNwBjjOnQKdIt5nVCjPeRDpSgA=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=bkTPFfoa5Q6RihfB2yZ0VMy8sqJj4mhwuzMoPpurfSm00x10jF+lRb6Jl4lXGIh+H\n\t9FAdStvNp2o+v3VzRcb2VpahZnlp9hOQTtMvdRXcxc6C4uo6yLvcSVq9NB9NoyhZiQ\n\tiVbMthp2dYqZjXxla9vZn3BH27ZPbcuaP+mU5vSc=","Date":"Tue, 20 Apr 2021 03:25:20 +0300","From":"Laurent Pinchart ","To":"Hirokazu Honda ","Message-ID":"","References":"<20210415043625.3346627-1-hiroh@chromium.org>","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"<20210415043625.3346627-1-hiroh@chromium.org>","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera-devel@lists.libcamera.org","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16422,"web_url":"https://patchwork.libcamera.org/comment/16422/","msgid":"","date":"2021-04-21T02:34:58","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":63,"url":"https://patchwork.libcamera.org/api/people/63/","name":"Hirokazu Honda","email":"hiroh@chromium.org"},"content":"Hi Laurent, Thanks for reviewing.\n\n\nOn Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart\n wrote:\n>\n> Hi Hiro,\n>\n> Thank you for the patch.\n>\n> On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > The original updateControls() has the assumption that ctrls and\n> > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > implementation though. This changes updateControls()\n> > implementation so that it works without the assumption.\n> >\n> > Signed-off-by: Hirokazu Honda \n> > ---\n> > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > 1 file changed, 13 insertions(+), 13 deletions(-)\n> >\n> > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > index d4a9bb75..8fd79934 100644\n> > --- a/src/libcamera/v4l2_device.cpp\n> > +++ b/src/libcamera/v4l2_device.cpp\n> > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > const struct v4l2_ext_control *v4l2Ctrls,\n> > unsigned int count)\n> > {\n> > - unsigned int i = 0;\n> > - for (auto &ctrl : *ctrls) {\n> > - if (i == count)\n> > - break;\n> > -\n> > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > - unsigned int id = ctrl.first;\n> > - ControlValue &value = ctrl.second;\n> > + for (unsigned int i = 0; i < count; i++) {\n> > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > + const unsigned int id = v4l2Ctrl.id;\n> > + if (!ctrls->contains(id)) {\n> > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > + << id;\n> > + return;\n> > + }\n> >\n> > - const auto iter = controls_.find(id);\n> > - switch (iter->first->type()) {\n> > + ControlValue value = ctrls->get(id);\n>\n> This is less efficient, as the function now runs with O(n^2) complexity.\n\nCan you explain me why the time complexity is O(n^2)?\nSince controls_ is based on std::unordered_map, find(), contains(),\nget() and set() should be O(1).\nSo I think this is still O(n).\n\n> Given that updateControls() is private, why is requiring ctrls and\n> v4l2Ctrls to have the same order a problem ? The requirement should be\n> documented, but does it cause any issue ?\n\nI think the restriction is strange and unnecessary, and a caller might\nhave to pre-process to keep that.\nWell, so far, the caller is only V4L2Device and we don't need anything\nto keep the rule.\n-Hiro\n\n>\n> > + switch (value.type()) {\n> > case ControlTypeInteger64:\n> > - value.set(v4l2Ctrl->value64);\n> > + value.set(v4l2Ctrl.value64);\n> > break;\n> >\n> > case ControlTypeByte:\n> > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > * \\todo To be changed when support for string controls\n> > * will be added.\n> > */\n> > - value.set(v4l2Ctrl->value);\n> > + value.set(v4l2Ctrl.value);\n> > break;\n> > }\n> >\n> > - i++;\n> > + ctrls->set(id, value);\n> > }\n> > }\n> >\n>\n> --\n> Regards,\n>\n> Laurent Pinchart","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id C666BBDB16\n\tfor ;\n\tWed, 21 Apr 2021 02:35:11 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id F39DB68840;\n\tWed, 21 Apr 2021 04:35:10 +0200 (CEST)","from mail-ej1-x635.google.com (mail-ej1-x635.google.com\n\t[IPv6:2a00:1450:4864:20::635])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 0C088602C8\n\tfor ;\n\tWed, 21 Apr 2021 04:35:10 +0200 (CEST)","by mail-ej1-x635.google.com with SMTP id w23so45438114ejb.9\n\tfor ;\n\tTue, 20 Apr 2021 19:35:10 -0700 (PDT)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=chromium.org header.i=@chromium.org\n\theader.b=\"ngSYL5lw\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org;\n\ts=google; \n\th=mime-version:references:in-reply-to:from:date:message-id:subject:to\n\t:cc; bh=ViDXEuhXmVk3sZLozespUrNlAGifu2/gRQYPPBfXRL4=;\n\tb=ngSYL5lwv3Wlh3Bni9oIq1QFSS8C+P6I91tW/AkD+qW1RXUmP8dzjwdbHWKl1ccIkp\n\tK9M4NehvZYGFcCctb/as3L36ufkdyugbYTEmy2n2jHPWr1cbIe/54IkeWMrtTkL9NgJN\n\t7UkE0wL1skS8prrVTPLP/aJxOpnD7ZNoz9vbU=","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:mime-version:references:in-reply-to:from:date\n\t:message-id:subject:to:cc;\n\tbh=ViDXEuhXmVk3sZLozespUrNlAGifu2/gRQYPPBfXRL4=;\n\tb=Cw1UmY9E/X6A7XnCyuhJTsnYZx6+D8owyD2DC/5MtxsETbpyjhkEE2CNhNMeSJiU4j\n\tlHPklVpAwkN9ShWTahMPRHZnkZqAbnzC7Ow7Vb4fIvYsToGBjnID8fAc2yLUvOnuDw9/\n\tZ3WaX6GGXCe606oBejt+WLALMiEOAbXPRalRh2kgB9GwKrq/UzxB7Zp3TBDsLRLcFs28\n\t5rzUMQqtecERhyOqROceyxWhdFh93BfEm9Jj84U6J4CX50gEdHZ7rrUB/Bn3GX1I03K6\n\ttyYSH901wYV/24UcRewgEkn38nSeTiSERRSTHprjfgynwZAJxEensRM/p3nG9TBzsoSk\n\t4cOg==","X-Gm-Message-State":"AOAM5321irwoqmO+XW9ViGbsLvJ0yv8ICKXhH9XKkckZk+NAa0zE7Klg\n\tjpgm9zQnWyjleTfEvHyIsvNSWlo7Obl+zQpybXIcZA==","X-Google-Smtp-Source":"ABdhPJzz5lc3Ve/Yv3sMh7zJDCNqlPLZDv9Y8kro4LblRuGf1cgb33Q+PV7WsNb3bZqqDF/wrQPFl5w06qMzLNES3Uk=","X-Received":"by 2002:a17:906:13d6:: with SMTP id\n\tg22mr30504318ejc.475.1618972509633; \n\tTue, 20 Apr 2021 19:35:09 -0700 (PDT)","MIME-Version":"1.0","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t","In-Reply-To":"","From":"Hirokazu Honda ","Date":"Wed, 21 Apr 2021 11:34:58 +0900","Message-ID":"","To":"Laurent Pinchart ","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16441,"web_url":"https://patchwork.libcamera.org/comment/16441/","msgid":"","date":"2021-04-21T09:30:50","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"Hi Hiro,\n\nOn Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:\n> On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:\n> > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > > The original updateControls() has the assumption that ctrls and\n> > > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > > implementation though. This changes updateControls()\n> > > implementation so that it works without the assumption.\n> > >\n> > > Signed-off-by: Hirokazu Honda \n> > > ---\n> > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > > 1 file changed, 13 insertions(+), 13 deletions(-)\n> > >\n> > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > > index d4a9bb75..8fd79934 100644\n> > > --- a/src/libcamera/v4l2_device.cpp\n> > > +++ b/src/libcamera/v4l2_device.cpp\n> > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > const struct v4l2_ext_control *v4l2Ctrls,\n> > > unsigned int count)\n> > > {\n> > > - unsigned int i = 0;\n> > > - for (auto &ctrl : *ctrls) {\n> > > - if (i == count)\n> > > - break;\n> > > -\n> > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > > - unsigned int id = ctrl.first;\n> > > - ControlValue &value = ctrl.second;\n> > > + for (unsigned int i = 0; i < count; i++) {\n> > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > > + const unsigned int id = v4l2Ctrl.id;\n> > > + if (!ctrls->contains(id)) {\n> > > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > > + << id;\n> > > + return;\n> > > + }\n> > >\n> > > - const auto iter = controls_.find(id);\n> > > - switch (iter->first->type()) {\n> > > + ControlValue value = ctrls->get(id);\n> >\n> > This is less efficient, as the function now runs with O(n^2) complexity.\n> \n> Can you explain me why the time complexity is O(n^2)?\n> Since controls_ is based on std::unordered_map, find(), contains(),\n> get() and set() should be O(1).\n> So I think this is still O(n).\n\nYou're right that it's not O(n^2) as we use an unordered map.\nstd::unordered_map::find() is \"constant on average, worst case linear in\nthe size of the container\".\n\n> > Given that updateControls() is private, why is requiring ctrls and\n> > v4l2Ctrls to have the same order a problem ? The requirement should be\n> > documented, but does it cause any issue ?\n> \n> I think the restriction is strange and unnecessary, and a caller might\n> have to pre-process to keep that.\n> Well, so far, the caller is only V4L2Device and we don't need anything\n> to keep the rule.\n\nThat was my point, it's a private function of the class :-) As all\ncallers currently guarantee the order, I'd defer this change until we\nhave a use case.\n\n> > > + switch (value.type()) {\n> > > case ControlTypeInteger64:\n> > > - value.set(v4l2Ctrl->value64);\n> > > + value.set(v4l2Ctrl.value64);\n> > > break;\n> > >\n> > > case ControlTypeByte:\n> > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > * \\todo To be changed when support for string controls\n> > > * will be added.\n> > > */\n> > > - value.set(v4l2Ctrl->value);\n> > > + value.set(v4l2Ctrl.value);\n> > > break;\n> > > }\n> > >\n> > > - i++;\n> > > + ctrls->set(id, value);\n> > > }\n> > > }\n> > >","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 2CDC3BDB16\n\tfor ;\n\tWed, 21 Apr 2021 09:30:57 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 650EB68844;\n\tWed, 21 Apr 2021 11:30:56 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 77F9D602D1\n\tfor ;\n\tWed, 21 Apr 2021 11:30:55 +0200 (CEST)","from pendragon.ideasonboard.com (62-78-145-57.bb.dnainternet.fi\n\t[62.78.145.57])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id E719A3EE;\n\tWed, 21 Apr 2021 11:30:54 +0200 (CEST)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"AXJe69VX\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1618997455;\n\tbh=vHXINJebSKg1edrYCFCIOqcAPytDydLuzfMvgvbZSGc=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=AXJe69VX0BpDcs2NuSh6XXiay+LcqKXu5J4vYQ3t+qoJ2ghvGRribsficHs09O72s\n\tnlCtXvjapcVY0C+3ES7MfpLWIVcP9cCKk/mOAt6Nw9jbHvVGbT4Dj9vf/E/8y+8Tuf\n\tyxvSgkMQWURBw1sls6vT8fvzb5uAzodk1XQ0VlU0=","Date":"Wed, 21 Apr 2021 12:30:50 +0300","From":"Laurent Pinchart ","To":"Hirokazu Honda ","Message-ID":"","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t\n\t","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16445,"web_url":"https://patchwork.libcamera.org/comment/16445/","msgid":"","date":"2021-04-21T09:37:45","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":63,"url":"https://patchwork.libcamera.org/api/people/63/","name":"Hirokazu Honda","email":"hiroh@chromium.org"},"content":"On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart\n wrote:\n>\n> Hi Hiro,\n>\n> On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:\n> > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:\n> > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > > > The original updateControls() has the assumption that ctrls and\n> > > > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > > > implementation though. This changes updateControls()\n> > > > implementation so that it works without the assumption.\n> > > >\n> > > > Signed-off-by: Hirokazu Honda \n> > > > ---\n> > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > > > 1 file changed, 13 insertions(+), 13 deletions(-)\n> > > >\n> > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > > > index d4a9bb75..8fd79934 100644\n> > > > --- a/src/libcamera/v4l2_device.cpp\n> > > > +++ b/src/libcamera/v4l2_device.cpp\n> > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > const struct v4l2_ext_control *v4l2Ctrls,\n> > > > unsigned int count)\n> > > > {\n> > > > - unsigned int i = 0;\n> > > > - for (auto &ctrl : *ctrls) {\n> > > > - if (i == count)\n> > > > - break;\n> > > > -\n> > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > > > - unsigned int id = ctrl.first;\n> > > > - ControlValue &value = ctrl.second;\n> > > > + for (unsigned int i = 0; i < count; i++) {\n> > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > > > + const unsigned int id = v4l2Ctrl.id;\n> > > > + if (!ctrls->contains(id)) {\n> > > > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > > > + << id;\n> > > > + return;\n> > > > + }\n> > > >\n> > > > - const auto iter = controls_.find(id);\n> > > > - switch (iter->first->type()) {\n> > > > + ControlValue value = ctrls->get(id);\n> > >\n> > > This is less efficient, as the function now runs with O(n^2) complexity.\n> >\n> > Can you explain me why the time complexity is O(n^2)?\n> > Since controls_ is based on std::unordered_map, find(), contains(),\n> > get() and set() should be O(1).\n> > So I think this is still O(n).\n>\n> You're right that it's not O(n^2) as we use an unordered map.\n> std::unordered_map::find() is \"constant on average, worst case linear in\n> the size of the container\".\n>\n> > > Given that updateControls() is private, why is requiring ctrls and\n> > > v4l2Ctrls to have the same order a problem ? The requirement should be\n> > > documented, but does it cause any issue ?\n> >\n> > I think the restriction is strange and unnecessary, and a caller might\n> > have to pre-process to keep that.\n> > Well, so far, the caller is only V4L2Device and we don't need anything\n> > to keep the rule.\n>\n> That was my point, it's a private function of the class :-) As all\n> callers currently guarantee the order, I'd defer this change until we\n> have a use case.\n>\n\nI forgot mentioning there is no guaranteed upon traversing std::unordered_map.\nhttps://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c\n\nSo I think as long as std::unordered_map is used, the original\nimplementation is problematic?\n-Hiro\n\n> > > > + switch (value.type()) {\n> > > > case ControlTypeInteger64:\n> > > > - value.set(v4l2Ctrl->value64);\n> > > > + value.set(v4l2Ctrl.value64);\n> > > > break;\n> > > >\n> > > > case ControlTypeByte:\n> > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > * \\todo To be changed when support for string controls\n> > > > * will be added.\n> > > > */\n> > > > - value.set(v4l2Ctrl->value);\n> > > > + value.set(v4l2Ctrl.value);\n> > > > break;\n> > > > }\n> > > >\n> > > > - i++;\n> > > > + ctrls->set(id, value);\n> > > > }\n> > > > }\n> > > >\n>\n> --\n> Regards,\n>\n> Laurent Pinchart","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 27021BDB16\n\tfor ;\n\tWed, 21 Apr 2021 09:37:58 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 7E70168844;\n\tWed, 21 Apr 2021 11:37:57 +0200 (CEST)","from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com\n\t[IPv6:2a00:1450:4864:20::52d])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id D13FC68806\n\tfor ;\n\tWed, 21 Apr 2021 11:37:55 +0200 (CEST)","by mail-ed1-x52d.google.com with SMTP id h10so48525436edt.13\n\tfor ;\n\tWed, 21 Apr 2021 02:37:55 -0700 (PDT)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=chromium.org header.i=@chromium.org\n\theader.b=\"K1/8Dn0o\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org;\n\ts=google; \n\th=mime-version:references:in-reply-to:from:date:message-id:subject:to\n\t:cc; bh=YM97HeUD8RiZcAaJJwfYr/SQz6HUtjIfsvQgmjehsvE=;\n\tb=K1/8Dn0otbhajM+etOg501stLZY/NbrwRaV2bqc5MHQRsE2pJwCtzzH/y5TN44WUwg\n\t/BvBx3C2bo/NY7mzCuJNQghoD6QnUeP1arbaINCLX+Ok31i6bTjGkAGotmFwHMMbzCiz\n\tSMmE8UBkHB+nLteBDw1yzwzWvLzKHB1qb9xik=","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:mime-version:references:in-reply-to:from:date\n\t:message-id:subject:to:cc;\n\tbh=YM97HeUD8RiZcAaJJwfYr/SQz6HUtjIfsvQgmjehsvE=;\n\tb=E06eJvNB5rfeWMrRJFJiJUpo+xxqu4KMlXk+egFcY3iHlWcyr+Lc3QEXpHTzucNtze\n\trvTY4zkqYT1I1lzk7UmAO09Ic3hxCpawTekeOND3PXLPIbSGNsCLTUZzdHSSXAHGS4ZQ\n\tkWZbkRipHW7fpPx35z7VK/OSXQGoIRZZeOkowoEJ2uc6YEUTaKJ6Wd424vtSXqs28nz/\n\tT4sgtj/7l8klsfQfkPGSJs5mnDc0XwZR2wU6hQUJGS5K2NM0/kItvEpYStxxcWiFVDNM\n\t+TwQIEjDuWXy+4js7ezF1gdwxV4atZIro/09GXp4ko4tRXNa+IIElR2SpCIViVZefFIz\n\tc2+Q==","X-Gm-Message-State":"AOAM532YXwWWpS0sxPeQDpOD0jK7rhCJtn8v1BS8tlU1hBcz766nTrkc\n\tbippK0g46ZGdvz/dfcN+MtoUYCvs5OmqJktE6w29fA==","X-Google-Smtp-Source":"ABdhPJwPcmGUnKfDGARsGKWa8jR4qKKTbX0REbsxMn8wxmc8zrv2Nj1hwijIjNw+ohg0THMwUe+IhVcHd6+/2CUiqYo=","X-Received":"by 2002:a05:6402:5211:: with SMTP id\n\ts17mr37789449edd.327.1618997875446; \n\tWed, 21 Apr 2021 02:37:55 -0700 (PDT)","MIME-Version":"1.0","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t\n\t\n\t","In-Reply-To":"","From":"Hirokazu Honda ","Date":"Wed, 21 Apr 2021 18:37:45 +0900","Message-ID":"","To":"Laurent Pinchart ","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16451,"web_url":"https://patchwork.libcamera.org/comment/16451/","msgid":"<20210421123733.kd3zzzqwfixinuvg@uno.localdomain>","date":"2021-04-21T12:37:33","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":3,"url":"https://patchwork.libcamera.org/api/people/3/","name":"Jacopo Mondi","email":"jacopo@jmondi.org"},"content":"Hi Hiro,\n\nOn Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote:\n> On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart\n> wrote:\n> >\n> > Hi Hiro,\n> >\n> > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:\n> > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:\n> > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > > > > The original updateControls() has the assumption that ctrls and\n> > > > > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > > > > implementation though. This changes updateControls()\n> > > > > implementation so that it works without the assumption.\n> > > > >\n> > > > > Signed-off-by: Hirokazu Honda \n> > > > > ---\n> > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > > > > 1 file changed, 13 insertions(+), 13 deletions(-)\n> > > > >\n> > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > > > > index d4a9bb75..8fd79934 100644\n> > > > > --- a/src/libcamera/v4l2_device.cpp\n> > > > > +++ b/src/libcamera/v4l2_device.cpp\n> > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > const struct v4l2_ext_control *v4l2Ctrls,\n> > > > > unsigned int count)\n> > > > > {\n> > > > > - unsigned int i = 0;\n> > > > > - for (auto &ctrl : *ctrls) {\n> > > > > - if (i == count)\n> > > > > - break;\n> > > > > -\n> > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > > > > - unsigned int id = ctrl.first;\n> > > > > - ControlValue &value = ctrl.second;\n> > > > > + for (unsigned int i = 0; i < count; i++) {\n> > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > > > > + const unsigned int id = v4l2Ctrl.id;\n> > > > > + if (!ctrls->contains(id)) {\n> > > > > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > > > > + << id;\n> > > > > + return;\n> > > > > + }\n> > > > >\n> > > > > - const auto iter = controls_.find(id);\n> > > > > - switch (iter->first->type()) {\n> > > > > + ControlValue value = ctrls->get(id);\n> > > >\n> > > > This is less efficient, as the function now runs with O(n^2) complexity.\n> > >\n> > > Can you explain me why the time complexity is O(n^2)?\n> > > Since controls_ is based on std::unordered_map, find(), contains(),\n> > > get() and set() should be O(1).\n> > > So I think this is still O(n).\n\nI read that all these functions are \"in worst case\" linear to the\nlength of the input in complexity\n\n> >\n> > You're right that it's not O(n^2) as we use an unordered map.\n> > std::unordered_map::find() is \"constant on average, worst case linear in\n> > the size of the container\".\n> >\n> > > > Given that updateControls() is private, why is requiring ctrls and\n> > > > v4l2Ctrls to have the same order a problem ? The requirement should be\n> > > > documented, but does it cause any issue ?\n> > >\n> > > I think the restriction is strange and unnecessary, and a caller might\n> > > have to pre-process to keep that.\n> > > Well, so far, the caller is only V4L2Device and we don't need anything\n> > > to keep the rule.\n> >\n> > That was my point, it's a private function of the class :-) As all\n> > callers currently guarantee the order, I'd defer this change until we\n> > have a use case.\n> >\n>\n> I forgot mentioning there is no guaranteed upon traversing std::unordered_map.\n> https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c\n>\n> So I think as long as std::unordered_map is used, the original\n> implementation is problematic?\n\nIf you look at the callers, the v4l2Ctrls are filled in by iterating\non the ControlList (which is an unordered map).\n\nRegardless of how the ControlList is sorted, v4l2Ctrls will have the\nsame sorting order. There's a comment that explains that in\ngetControls():\n\n\t/*\n\t * Start by filling the ControlList. This can't be combined with filling\n\t * v4l2Ctrls, as updateControls() relies on both containers having the\n\t * same order, and the control list is based on a map, which is not\n\t * sorted by insertion order.\n\t */\n\nI might have missed what issue you have encountered.\n\nI'm anyway not opposed to this change, as the ordering assumption is a\nbit weird, even if it should be safe.\n\nChanging such a core feature would require some careful testing, and\nif there's no actual reason to change it I would be cautious to do so\nbut I'm not opposed...\n\n\n> -Hiro\n>\n> > > > > + switch (value.type()) {\n> > > > > case ControlTypeInteger64:\n> > > > > - value.set(v4l2Ctrl->value64);\n> > > > > + value.set(v4l2Ctrl.value64);\n> > > > > break;\n> > > > >\n> > > > > case ControlTypeByte:\n> > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > * \\todo To be changed when support for string controls\n> > > > > * will be added.\n> > > > > */\n> > > > > - value.set(v4l2Ctrl->value);\n> > > > > + value.set(v4l2Ctrl.value);\n> > > > > break;\n> > > > > }\n> > > > >\n> > > > > - i++;\n> > > > > + ctrls->set(id, value);\n> > > > > }\n> > > > > }\n> > > > >\n> >\n> > --\n> > Regards,\n> >\n> > Laurent Pinchart\n> _______________________________________________\n> libcamera-devel mailing list\n> libcamera-devel@lists.libcamera.org\n> https://lists.libcamera.org/listinfo/libcamera-devel","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id C5257BDB15\n\tfor ;\n\tWed, 21 Apr 2021 12:36:54 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 22C0C68849;\n\tWed, 21 Apr 2021 14:36:54 +0200 (CEST)","from relay6-d.mail.gandi.net (relay6-d.mail.gandi.net\n\t[217.70.183.198])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id D387068835\n\tfor ;\n\tWed, 21 Apr 2021 14:36:52 +0200 (CEST)","from uno.localdomain (93-34-118-233.ip49.fastwebnet.it\n\t[93.34.118.233]) (Authenticated sender: jacopo@jmondi.org)\n\tby relay6-d.mail.gandi.net (Postfix) with ESMTPSA id 2072CC0003;\n\tWed, 21 Apr 2021 12:36:51 +0000 (UTC)"],"X-Originating-IP":"93.34.118.233","Date":"Wed, 21 Apr 2021 14:37:33 +0200","From":"Jacopo Mondi ","To":"Hirokazu Honda ","Message-ID":"<20210421123733.kd3zzzqwfixinuvg@uno.localdomain>","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t\n\t\n\t\n\t","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16473,"web_url":"https://patchwork.libcamera.org/comment/16473/","msgid":"","date":"2021-04-22T02:14:59","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":63,"url":"https://patchwork.libcamera.org/api/people/63/","name":"Hirokazu Honda","email":"hiroh@chromium.org"},"content":"On Wed, Apr 21, 2021 at 9:36 PM Jacopo Mondi wrote:\n>\n> Hi Hiro,\n>\n> On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote:\n> > On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart\n> > wrote:\n> > >\n> > > Hi Hiro,\n> > >\n> > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:\n> > > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:\n> > > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > > > > > The original updateControls() has the assumption that ctrls and\n> > > > > > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > > > > > implementation though. This changes updateControls()\n> > > > > > implementation so that it works without the assumption.\n> > > > > >\n> > > > > > Signed-off-by: Hirokazu Honda \n> > > > > > ---\n> > > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > > > > > 1 file changed, 13 insertions(+), 13 deletions(-)\n> > > > > >\n> > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > > > > > index d4a9bb75..8fd79934 100644\n> > > > > > --- a/src/libcamera/v4l2_device.cpp\n> > > > > > +++ b/src/libcamera/v4l2_device.cpp\n> > > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > > const struct v4l2_ext_control *v4l2Ctrls,\n> > > > > > unsigned int count)\n> > > > > > {\n> > > > > > - unsigned int i = 0;\n> > > > > > - for (auto &ctrl : *ctrls) {\n> > > > > > - if (i == count)\n> > > > > > - break;\n> > > > > > -\n> > > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > > > > > - unsigned int id = ctrl.first;\n> > > > > > - ControlValue &value = ctrl.second;\n> > > > > > + for (unsigned int i = 0; i < count; i++) {\n> > > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > > > > > + const unsigned int id = v4l2Ctrl.id;\n> > > > > > + if (!ctrls->contains(id)) {\n> > > > > > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > > > > > + << id;\n> > > > > > + return;\n> > > > > > + }\n> > > > > >\n> > > > > > - const auto iter = controls_.find(id);\n> > > > > > - switch (iter->first->type()) {\n> > > > > > + ControlValue value = ctrls->get(id);\n> > > > >\n> > > > > This is less efficient, as the function now runs with O(n^2) complexity.\n> > > >\n> > > > Can you explain me why the time complexity is O(n^2)?\n> > > > Since controls_ is based on std::unordered_map, find(), contains(),\n> > > > get() and set() should be O(1).\n> > > > So I think this is still O(n).\n>\n> I read that all these functions are \"in worst case\" linear to the\n> length of the input in complexity\n>\n> > >\n> > > You're right that it's not O(n^2) as we use an unordered map.\n> > > std::unordered_map::find() is \"constant on average, worst case linear in\n> > > the size of the container\".\n> > >\n> > > > > Given that updateControls() is private, why is requiring ctrls and\n> > > > > v4l2Ctrls to have the same order a problem ? The requirement should be\n> > > > > documented, but does it cause any issue ?\n> > > >\n> > > > I think the restriction is strange and unnecessary, and a caller might\n> > > > have to pre-process to keep that.\n> > > > Well, so far, the caller is only V4L2Device and we don't need anything\n> > > > to keep the rule.\n> > >\n> > > That was my point, it's a private function of the class :-) As all\n> > > callers currently guarantee the order, I'd defer this change until we\n> > > have a use case.\n> > >\n> >\n> > I forgot mentioning there is no guaranteed upon traversing std::unordered_map.\n> > https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c\n> >\n> > So I think as long as std::unordered_map is used, the original\n> > implementation is problematic?\n>\n> If you look at the callers, the v4l2Ctrls are filled in by iterating\n> on the ControlList (which is an unordered map).\n>\n> Regardless of how the ControlList is sorted, v4l2Ctrls will have the\n> same sorting order. There's a comment that explains that in\n> getControls():\n>\n> /*\n> * Start by filling the ControlList. This can't be combined with filling\n> * v4l2Ctrls, as updateControls() relies on both containers having the\n> * same order, and the control list is based on a map, which is not\n> * sorted by insertion order.\n> */\n>\n\nThanks. I missed this comment.\n\n> I might have missed what issue you have encountered.\n>\n> I'm anyway not opposed to this change, as the ordering assumption is a\n> bit weird, even if it should be safe.\n>\n> Changing such a core feature would require some careful testing, and\n> if there's no actual reason to change it I would be cautious to do so\n> but I'm not opposed...\n>\n\nI actually have never faced any issue due to this.\nAs a reader, this assumption is unnecessary and thus feels strange for me.\nRemoving the assumption is simple enough I believe, so I hope this\nchange makes sense to everyone.\n-Hiro\n\n>\n> > -Hiro\n> >\n> > > > > > + switch (value.type()) {\n> > > > > > case ControlTypeInteger64:\n> > > > > > - value.set(v4l2Ctrl->value64);\n> > > > > > + value.set(v4l2Ctrl.value64);\n> > > > > > break;\n> > > > > >\n> > > > > > case ControlTypeByte:\n> > > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > > * \\todo To be changed when support for string controls\n> > > > > > * will be added.\n> > > > > > */\n> > > > > > - value.set(v4l2Ctrl->value);\n> > > > > > + value.set(v4l2Ctrl.value);\n> > > > > > break;\n> > > > > > }\n> > > > > >\n> > > > > > - i++;\n> > > > > > + ctrls->set(id, value);\n> > > > > > }\n> > > > > > }\n> > > > > >\n> > >\n> > > --\n> > > Regards,\n> > >\n> > > Laurent Pinchart\n> > _______________________________________________\n> > libcamera-devel mailing list\n> > libcamera-devel@lists.libcamera.org\n> > https://lists.libcamera.org/listinfo/libcamera-devel","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id D8046BDB17\n\tfor ;\n\tThu, 22 Apr 2021 02:15:12 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 43B7168849;\n\tThu, 22 Apr 2021 04:15:12 +0200 (CEST)","from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com\n\t[IPv6:2a00:1450:4864:20::62a])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id BE04D60516\n\tfor ;\n\tThu, 22 Apr 2021 04:15:10 +0200 (CEST)","by mail-ej1-x62a.google.com with SMTP id l4so66321844ejc.10\n\tfor ;\n\tWed, 21 Apr 2021 19:15:10 -0700 (PDT)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=chromium.org header.i=@chromium.org\n\theader.b=\"ex98blO/\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org;\n\ts=google; \n\th=mime-version:references:in-reply-to:from:date:message-id:subject:to\n\t:cc; bh=4Pog2QB8gPUPMdvj0DKSlast9X9euMF7wcbj4bjimgo=;\n\tb=ex98blO/2TcHjlXIzpCrhDLvH/ID9E/DwQQF4+DbJITrroiZTpUBC1TTTvjsupHavT\n\tCw4qSP259lk2yr4Iafcbel4tCxMDfJ6oaAw3uJh0Sw4HyhEKBCgjYqLFNROD+JP88mTH\n\t4l6idS41QQ/GTH0NFtsO6kPXZeTUZpJbrG4kc=","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:mime-version:references:in-reply-to:from:date\n\t:message-id:subject:to:cc;\n\tbh=4Pog2QB8gPUPMdvj0DKSlast9X9euMF7wcbj4bjimgo=;\n\tb=cyPF3PaVb9yQH7mzTDy/m1k1X7MRYnkjtyQB+QA7GrHQs5SzNtDo/dPDixB6UVBB6Z\n\tLZ1QOQq1C4yyNUQE4GYSNM0A3ZikQDXfV5U4RAl/xMLAK435LLuruvpB/PmDa81/ubTe\n\tVtQtMmqyAWZWHvmdXFWzFXbghQ9hwrISzg7sI0fnTXA1iSfi0cWxb62AXYAVVtUlsSqv\n\tDU9cSLXa3Box+1RHYV+S2cLye5bTMAN39nNnZGoj1UVHXffwbMtDt0WdLH1D1zFOxXW9\n\t4P4ZnjipSqBBRdNOa6P15hFbr4Be3WLSAFroBSqVd9D3zK44vQsvKjpp1Ek3RZ3+0zTB\n\tTL8g==","X-Gm-Message-State":"AOAM532DgUjskeb0O5a6chg0mGbSYiA3bkvUamel5VxSzEVg9tZ1Xogd\n\tgmK3NPLcNktDMu+AhEnUWaYl9gXzjdsxXrC+jdW2f1YQwqg=","X-Google-Smtp-Source":"ABdhPJy4g1rjF8g53ywSVZfVpG6eWdi6QBhnMWsD6a/YQ5osrGwL/TbDg0DzLGxMQPoLFzoLPFIwx/52ldvE3Cy5oz0=","X-Received":"by 2002:a17:906:fcc4:: with SMTP id\n\tqx4mr824683ejb.42.1619057710377; \n\tWed, 21 Apr 2021 19:15:10 -0700 (PDT)","MIME-Version":"1.0","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t\n\t\n\t\n\t\n\t<20210421123733.kd3zzzqwfixinuvg@uno.localdomain>","In-Reply-To":"<20210421123733.kd3zzzqwfixinuvg@uno.localdomain>","From":"Hirokazu Honda ","Date":"Thu, 22 Apr 2021 11:14:59 +0900","Message-ID":"","To":"Jacopo Mondi ","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}},{"id":16489,"web_url":"https://patchwork.libcamera.org/comment/16489/","msgid":"<20210422061633.owzu3pihjacbsfdn@uno.localdomain>","date":"2021-04-22T06:16:33","subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","submitter":{"id":3,"url":"https://patchwork.libcamera.org/api/people/3/","name":"Jacopo Mondi","email":"jacopo@jmondi.org"},"content":"Hi Hiro,\n\nOne more comment on the patch itself\n\n\nOn Thu, Apr 22, 2021 at 11:14:59AM +0900, Hirokazu Honda wrote:\n> On Wed, Apr 21, 2021 at 9:36 PM Jacopo Mondi wrote:\n> >\n> > Hi Hiro,\n> >\n> > On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote:\n> > > On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart\n> > > wrote:\n> > > >\n> > > > Hi Hiro,\n> > > >\n> > > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:\n> > > > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:\n> > > > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:\n> > > > > > > The original updateControls() has the assumption that ctrls and\n> > > > > > > v4l2Ctrls lists in the same order. It is dependent on the caller\n> > > > > > > implementation though. This changes updateControls()\n> > > > > > > implementation so that it works without the assumption.\n> > > > > > >\n> > > > > > > Signed-off-by: Hirokazu Honda \n> > > > > > > ---\n> > > > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------\n> > > > > > > 1 file changed, 13 insertions(+), 13 deletions(-)\n> > > > > > >\n> > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp\n> > > > > > > index d4a9bb75..8fd79934 100644\n> > > > > > > --- a/src/libcamera/v4l2_device.cpp\n> > > > > > > +++ b/src/libcamera/v4l2_device.cpp\n> > > > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > > > const struct v4l2_ext_control *v4l2Ctrls,\n> > > > > > > unsigned int count)\n> > > > > > > {\n> > > > > > > - unsigned int i = 0;\n> > > > > > > - for (auto &ctrl : *ctrls) {\n> > > > > > > - if (i == count)\n> > > > > > > - break;\n> > > > > > > -\n> > > > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];\n> > > > > > > - unsigned int id = ctrl.first;\n> > > > > > > - ControlValue &value = ctrl.second;\n> > > > > > > + for (unsigned int i = 0; i < count; i++) {\n> > > > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];\n> > > > > > > + const unsigned int id = v4l2Ctrl.id;\n> > > > > > > + if (!ctrls->contains(id)) {\n> > > > > > > + LOG(V4L2, Error) << \"ControlList doesn't contain id: \"\n> > > > > > > + << id;\n> > > > > > > + return;\n> > > > > > > + }\n\nThis can't happen, as this is a private function and we control the\ncallers\n\n> > > > > > >\n> > > > > > > - const auto iter = controls_.find(id);\n> > > > > > > - switch (iter->first->type()) {\n> > > > > > > + ControlValue value = ctrls->get(id);\n> > > > > >\n> > > > > > This is less efficient, as the function now runs with O(n^2) complexity.\n> > > > >\n> > > > > Can you explain me why the time complexity is O(n^2)?\n> > > > > Since controls_ is based on std::unordered_map, find(), contains(),\n> > > > > get() and set() should be O(1).\n> > > > > So I think this is still O(n).\n> >\n> > I read that all these functions are \"in worst case\" linear to the\n> > length of the input in complexity\n> >\n> > > >\n> > > > You're right that it's not O(n^2) as we use an unordered map.\n> > > > std::unordered_map::find() is \"constant on average, worst case linear in\n> > > > the size of the container\".\n> > > >\n> > > > > > Given that updateControls() is private, why is requiring ctrls and\n> > > > > > v4l2Ctrls to have the same order a problem ? The requirement should be\n> > > > > > documented, but does it cause any issue ?\n> > > > >\n> > > > > I think the restriction is strange and unnecessary, and a caller might\n> > > > > have to pre-process to keep that.\n> > > > > Well, so far, the caller is only V4L2Device and we don't need anything\n> > > > > to keep the rule.\n> > > >\n> > > > That was my point, it's a private function of the class :-) As all\n> > > > callers currently guarantee the order, I'd defer this change until we\n> > > > have a use case.\n> > > >\n> > >\n> > > I forgot mentioning there is no guaranteed upon traversing std::unordered_map.\n> > > https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c\n> > >\n> > > So I think as long as std::unordered_map is used, the original\n> > > implementation is problematic?\n> >\n> > If you look at the callers, the v4l2Ctrls are filled in by iterating\n> > on the ControlList (which is an unordered map).\n> >\n> > Regardless of how the ControlList is sorted, v4l2Ctrls will have the\n> > same sorting order. There's a comment that explains that in\n> > getControls():\n> >\n> > /*\n> > * Start by filling the ControlList. This can't be combined with filling\n> > * v4l2Ctrls, as updateControls() relies on both containers having the\n> > * same order, and the control list is based on a map, which is not\n> > * sorted by insertion order.\n> > */\n> >\n>\n> Thanks. I missed this comment.\n>\n> > I might have missed what issue you have encountered.\n> >\n> > I'm anyway not opposed to this change, as the ordering assumption is a\n> > bit weird, even if it should be safe.\n> >\n> > Changing such a core feature would require some careful testing, and\n> > if there's no actual reason to change it I would be cautious to do so\n> > but I'm not opposed...\n> >\n>\n> I actually have never faced any issue due to this.\n> As a reader, this assumption is unnecessary and thus feels strange for me.\n> Removing the assumption is simple enough I believe, so I hope this\n> change makes sense to everyone.\n> -Hiro\n>\n\nMakes sense, the caller should be updated too to remove the\nassumption too then, ideally removing the double for loop in\ngetControls().\n\nThe test covers updateControls() enough that making sure they pass\nit's ok to consier this change safe.\n\nThanks\n j\n\n\n> >\n> > > -Hiro\n> > >\n> > > > > > > + switch (value.type()) {\n> > > > > > > case ControlTypeInteger64:\n> > > > > > > - value.set(v4l2Ctrl->value64);\n> > > > > > > + value.set(v4l2Ctrl.value64);\n> > > > > > > break;\n> > > > > > >\n> > > > > > > case ControlTypeByte:\n> > > > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,\n> > > > > > > * \\todo To be changed when support for string controls\n> > > > > > > * will be added.\n> > > > > > > */\n> > > > > > > - value.set(v4l2Ctrl->value);\n> > > > > > > + value.set(v4l2Ctrl.value);\n> > > > > > > break;\n> > > > > > > }\n> > > > > > >\n> > > > > > > - i++;\n> > > > > > > + ctrls->set(id, value);\n> > > > > > > }\n> > > > > > > }\n> > > > > > >\n> > > >\n> > > > --\n> > > > Regards,\n> > > >\n> > > > Laurent Pinchart\n> > > _______________________________________________\n> > > libcamera-devel mailing list\n> > > libcamera-devel@lists.libcamera.org\n> > > https://lists.libcamera.org/listinfo/libcamera-devel","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id EB554BDB17\n\tfor ;\n\tThu, 22 Apr 2021 06:15:56 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 6094268852;\n\tThu, 22 Apr 2021 08:15:56 +0200 (CEST)","from relay9-d.mail.gandi.net (relay9-d.mail.gandi.net\n\t[217.70.183.199])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 274E96884B\n\tfor ;\n\tThu, 22 Apr 2021 08:15:54 +0200 (CEST)","from uno.localdomain (host-82-57-193-192.retail.telecomitalia.it\n\t[82.57.193.192]) (Authenticated sender: jacopo@jmondi.org)\n\tby relay9-d.mail.gandi.net (Postfix) with ESMTPSA id E0ED0FF810;\n\tThu, 22 Apr 2021 06:15:52 +0000 (UTC)"],"X-Originating-IP":"82.57.193.192","Date":"Thu, 22 Apr 2021 08:16:33 +0200","From":"Jacopo Mondi ","To":"Hirokazu Honda ","Message-ID":"<20210422061633.owzu3pihjacbsfdn@uno.localdomain>","References":"<20210415043625.3346627-1-hiroh@chromium.org>\n\t\n\t\n\t\n\t\n\t<20210421123733.kd3zzzqwfixinuvg@uno.localdomain>\n\t","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"","Subject":"Re: [libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the\n\tcontrols order assumption in updateControls()","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","Cc":"libcamera devel ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}}]