| Message ID | 20210415043625.3346627-1-hiroh@chromium.org |
|---|---|
| State | Superseded |
| Headers | show |
| Series |
|
| Related | show |
Hi Hiro, Thank you for the patch. On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > The original updateControls() has the assumption that ctrls and > v4l2Ctrls lists in the same order. It is dependent on the caller > implementation though. This changes updateControls() > implementation so that it works without the assumption. > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > --- > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > 1 file changed, 13 insertions(+), 13 deletions(-) > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > index d4a9bb75..8fd79934 100644 > --- a/src/libcamera/v4l2_device.cpp > +++ b/src/libcamera/v4l2_device.cpp > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > const struct v4l2_ext_control *v4l2Ctrls, > unsigned int count) > { > - unsigned int i = 0; > - for (auto &ctrl : *ctrls) { > - if (i == count) > - break; > - > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > - unsigned int id = ctrl.first; > - ControlValue &value = ctrl.second; > + for (unsigned int i = 0; i < count; i++) { > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > + const unsigned int id = v4l2Ctrl.id; > + if (!ctrls->contains(id)) { > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > + << id; > + return; > + } > > - const auto iter = controls_.find(id); > - switch (iter->first->type()) { > + ControlValue value = ctrls->get(id); This is less efficient, as the function now runs with O(n^2) complexity. Given that updateControls() is private, why is requiring ctrls and v4l2Ctrls to have the same order a problem ? The requirement should be documented, but does it cause any issue ? > + switch (value.type()) { > case ControlTypeInteger64: > - value.set<int64_t>(v4l2Ctrl->value64); > + value.set<int64_t>(v4l2Ctrl.value64); > break; > > case ControlTypeByte: > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > * \todo To be changed when support for string controls > * will be added. > */ > - value.set<int32_t>(v4l2Ctrl->value); > + value.set<int32_t>(v4l2Ctrl.value); > break; > } > > - i++; > + ctrls->set(id, value); > } > } >
Hi Laurent, Thanks for reviewing. On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart <laurent.pinchart@ideasonboard.com> wrote: > > Hi Hiro, > > Thank you for the patch. > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > The original updateControls() has the assumption that ctrls and > > v4l2Ctrls lists in the same order. It is dependent on the caller > > implementation though. This changes updateControls() > > implementation so that it works without the assumption. > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > --- > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > index d4a9bb75..8fd79934 100644 > > --- a/src/libcamera/v4l2_device.cpp > > +++ b/src/libcamera/v4l2_device.cpp > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > const struct v4l2_ext_control *v4l2Ctrls, > > unsigned int count) > > { > > - unsigned int i = 0; > > - for (auto &ctrl : *ctrls) { > > - if (i == count) > > - break; > > - > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > - unsigned int id = ctrl.first; > > - ControlValue &value = ctrl.second; > > + for (unsigned int i = 0; i < count; i++) { > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > + const unsigned int id = v4l2Ctrl.id; > > + if (!ctrls->contains(id)) { > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > + << id; > > + return; > > + } > > > > - const auto iter = controls_.find(id); > > - switch (iter->first->type()) { > > + ControlValue value = ctrls->get(id); > > This is less efficient, as the function now runs with O(n^2) complexity. Can you explain me why the time complexity is O(n^2)? Since controls_ is based on std::unordered_map, find(), contains(), get() and set() should be O(1). So I think this is still O(n). > Given that updateControls() is private, why is requiring ctrls and > v4l2Ctrls to have the same order a problem ? The requirement should be > documented, but does it cause any issue ? I think the restriction is strange and unnecessary, and a caller might have to pre-process to keep that. Well, so far, the caller is only V4L2Device and we don't need anything to keep the rule. -Hiro > > > + switch (value.type()) { > > case ControlTypeInteger64: > > - value.set<int64_t>(v4l2Ctrl->value64); > > + value.set<int64_t>(v4l2Ctrl.value64); > > break; > > > > case ControlTypeByte: > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > * \todo To be changed when support for string controls > > * will be added. > > */ > > - value.set<int32_t>(v4l2Ctrl->value); > > + value.set<int32_t>(v4l2Ctrl.value); > > break; > > } > > > > - i++; > > + ctrls->set(id, value); > > } > > } > > > > -- > Regards, > > Laurent Pinchart
Hi Hiro, On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote: > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote: > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > > The original updateControls() has the assumption that ctrls and > > > v4l2Ctrls lists in the same order. It is dependent on the caller > > > implementation though. This changes updateControls() > > > implementation so that it works without the assumption. > > > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > > --- > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > > index d4a9bb75..8fd79934 100644 > > > --- a/src/libcamera/v4l2_device.cpp > > > +++ b/src/libcamera/v4l2_device.cpp > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > const struct v4l2_ext_control *v4l2Ctrls, > > > unsigned int count) > > > { > > > - unsigned int i = 0; > > > - for (auto &ctrl : *ctrls) { > > > - if (i == count) > > > - break; > > > - > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > > - unsigned int id = ctrl.first; > > > - ControlValue &value = ctrl.second; > > > + for (unsigned int i = 0; i < count; i++) { > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > > + const unsigned int id = v4l2Ctrl.id; > > > + if (!ctrls->contains(id)) { > > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > > + << id; > > > + return; > > > + } > > > > > > - const auto iter = controls_.find(id); > > > - switch (iter->first->type()) { > > > + ControlValue value = ctrls->get(id); > > > > This is less efficient, as the function now runs with O(n^2) complexity. > > Can you explain me why the time complexity is O(n^2)? > Since controls_ is based on std::unordered_map, find(), contains(), > get() and set() should be O(1). > So I think this is still O(n). You're right that it's not O(n^2) as we use an unordered map. std::unordered_map::find() is "constant on average, worst case linear in the size of the container". > > Given that updateControls() is private, why is requiring ctrls and > > v4l2Ctrls to have the same order a problem ? The requirement should be > > documented, but does it cause any issue ? > > I think the restriction is strange and unnecessary, and a caller might > have to pre-process to keep that. > Well, so far, the caller is only V4L2Device and we don't need anything > to keep the rule. That was my point, it's a private function of the class :-) As all callers currently guarantee the order, I'd defer this change until we have a use case. > > > + switch (value.type()) { > > > case ControlTypeInteger64: > > > - value.set<int64_t>(v4l2Ctrl->value64); > > > + value.set<int64_t>(v4l2Ctrl.value64); > > > break; > > > > > > case ControlTypeByte: > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > * \todo To be changed when support for string controls > > > * will be added. > > > */ > > > - value.set<int32_t>(v4l2Ctrl->value); > > > + value.set<int32_t>(v4l2Ctrl.value); > > > break; > > > } > > > > > > - i++; > > > + ctrls->set(id, value); > > > } > > > } > > >
On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart <laurent.pinchart@ideasonboard.com> wrote: > > Hi Hiro, > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote: > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote: > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > > > The original updateControls() has the assumption that ctrls and > > > > v4l2Ctrls lists in the same order. It is dependent on the caller > > > > implementation though. This changes updateControls() > > > > implementation so that it works without the assumption. > > > > > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > > > --- > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > > > index d4a9bb75..8fd79934 100644 > > > > --- a/src/libcamera/v4l2_device.cpp > > > > +++ b/src/libcamera/v4l2_device.cpp > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > const struct v4l2_ext_control *v4l2Ctrls, > > > > unsigned int count) > > > > { > > > > - unsigned int i = 0; > > > > - for (auto &ctrl : *ctrls) { > > > > - if (i == count) > > > > - break; > > > > - > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > > > - unsigned int id = ctrl.first; > > > > - ControlValue &value = ctrl.second; > > > > + for (unsigned int i = 0; i < count; i++) { > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > > > + const unsigned int id = v4l2Ctrl.id; > > > > + if (!ctrls->contains(id)) { > > > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > > > + << id; > > > > + return; > > > > + } > > > > > > > > - const auto iter = controls_.find(id); > > > > - switch (iter->first->type()) { > > > > + ControlValue value = ctrls->get(id); > > > > > > This is less efficient, as the function now runs with O(n^2) complexity. > > > > Can you explain me why the time complexity is O(n^2)? > > Since controls_ is based on std::unordered_map, find(), contains(), > > get() and set() should be O(1). > > So I think this is still O(n). > > You're right that it's not O(n^2) as we use an unordered map. > std::unordered_map::find() is "constant on average, worst case linear in > the size of the container". > > > > Given that updateControls() is private, why is requiring ctrls and > > > v4l2Ctrls to have the same order a problem ? The requirement should be > > > documented, but does it cause any issue ? > > > > I think the restriction is strange and unnecessary, and a caller might > > have to pre-process to keep that. > > Well, so far, the caller is only V4L2Device and we don't need anything > > to keep the rule. > > That was my point, it's a private function of the class :-) As all > callers currently guarantee the order, I'd defer this change until we > have a use case. > I forgot mentioning there is no guaranteed upon traversing std::unordered_map. https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c So I think as long as std::unordered_map is used, the original implementation is problematic? -Hiro > > > > + switch (value.type()) { > > > > case ControlTypeInteger64: > > > > - value.set<int64_t>(v4l2Ctrl->value64); > > > > + value.set<int64_t>(v4l2Ctrl.value64); > > > > break; > > > > > > > > case ControlTypeByte: > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > * \todo To be changed when support for string controls > > > > * will be added. > > > > */ > > > > - value.set<int32_t>(v4l2Ctrl->value); > > > > + value.set<int32_t>(v4l2Ctrl.value); > > > > break; > > > > } > > > > > > > > - i++; > > > > + ctrls->set(id, value); > > > > } > > > > } > > > > > > -- > Regards, > > Laurent Pinchart
Hi Hiro, On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote: > On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart > <laurent.pinchart@ideasonboard.com> wrote: > > > > Hi Hiro, > > > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote: > > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote: > > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > > > > The original updateControls() has the assumption that ctrls and > > > > > v4l2Ctrls lists in the same order. It is dependent on the caller > > > > > implementation though. This changes updateControls() > > > > > implementation so that it works without the assumption. > > > > > > > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > > > > --- > > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > > > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > > > > index d4a9bb75..8fd79934 100644 > > > > > --- a/src/libcamera/v4l2_device.cpp > > > > > +++ b/src/libcamera/v4l2_device.cpp > > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > const struct v4l2_ext_control *v4l2Ctrls, > > > > > unsigned int count) > > > > > { > > > > > - unsigned int i = 0; > > > > > - for (auto &ctrl : *ctrls) { > > > > > - if (i == count) > > > > > - break; > > > > > - > > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > > > > - unsigned int id = ctrl.first; > > > > > - ControlValue &value = ctrl.second; > > > > > + for (unsigned int i = 0; i < count; i++) { > > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > > > > + const unsigned int id = v4l2Ctrl.id; > > > > > + if (!ctrls->contains(id)) { > > > > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > > > > + << id; > > > > > + return; > > > > > + } > > > > > > > > > > - const auto iter = controls_.find(id); > > > > > - switch (iter->first->type()) { > > > > > + ControlValue value = ctrls->get(id); > > > > > > > > This is less efficient, as the function now runs with O(n^2) complexity. > > > > > > Can you explain me why the time complexity is O(n^2)? > > > Since controls_ is based on std::unordered_map, find(), contains(), > > > get() and set() should be O(1). > > > So I think this is still O(n). I read that all these functions are "in worst case" linear to the length of the input in complexity > > > > You're right that it's not O(n^2) as we use an unordered map. > > std::unordered_map::find() is "constant on average, worst case linear in > > the size of the container". > > > > > > Given that updateControls() is private, why is requiring ctrls and > > > > v4l2Ctrls to have the same order a problem ? The requirement should be > > > > documented, but does it cause any issue ? > > > > > > I think the restriction is strange and unnecessary, and a caller might > > > have to pre-process to keep that. > > > Well, so far, the caller is only V4L2Device and we don't need anything > > > to keep the rule. > > > > That was my point, it's a private function of the class :-) As all > > callers currently guarantee the order, I'd defer this change until we > > have a use case. > > > > I forgot mentioning there is no guaranteed upon traversing std::unordered_map. > https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c > > So I think as long as std::unordered_map is used, the original > implementation is problematic? If you look at the callers, the v4l2Ctrls are filled in by iterating on the ControlList (which is an unordered map). Regardless of how the ControlList is sorted, v4l2Ctrls will have the same sorting order. There's a comment that explains that in getControls(): /* * Start by filling the ControlList. This can't be combined with filling * v4l2Ctrls, as updateControls() relies on both containers having the * same order, and the control list is based on a map, which is not * sorted by insertion order. */ I might have missed what issue you have encountered. I'm anyway not opposed to this change, as the ordering assumption is a bit weird, even if it should be safe. Changing such a core feature would require some careful testing, and if there's no actual reason to change it I would be cautious to do so but I'm not opposed... > -Hiro > > > > > > + switch (value.type()) { > > > > > case ControlTypeInteger64: > > > > > - value.set<int64_t>(v4l2Ctrl->value64); > > > > > + value.set<int64_t>(v4l2Ctrl.value64); > > > > > break; > > > > > > > > > > case ControlTypeByte: > > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > * \todo To be changed when support for string controls > > > > > * will be added. > > > > > */ > > > > > - value.set<int32_t>(v4l2Ctrl->value); > > > > > + value.set<int32_t>(v4l2Ctrl.value); > > > > > break; > > > > > } > > > > > > > > > > - i++; > > > > > + ctrls->set(id, value); > > > > > } > > > > > } > > > > > > > > > -- > > Regards, > > > > Laurent Pinchart > _______________________________________________ > libcamera-devel mailing list > libcamera-devel@lists.libcamera.org > https://lists.libcamera.org/listinfo/libcamera-devel
On Wed, Apr 21, 2021 at 9:36 PM Jacopo Mondi <jacopo@jmondi.org> wrote: > > Hi Hiro, > > On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote: > > On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart > > <laurent.pinchart@ideasonboard.com> wrote: > > > > > > Hi Hiro, > > > > > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote: > > > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote: > > > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > > > > > The original updateControls() has the assumption that ctrls and > > > > > > v4l2Ctrls lists in the same order. It is dependent on the caller > > > > > > implementation though. This changes updateControls() > > > > > > implementation so that it works without the assumption. > > > > > > > > > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > > > > > --- > > > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > > > > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > > > > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > > > > > index d4a9bb75..8fd79934 100644 > > > > > > --- a/src/libcamera/v4l2_device.cpp > > > > > > +++ b/src/libcamera/v4l2_device.cpp > > > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > > const struct v4l2_ext_control *v4l2Ctrls, > > > > > > unsigned int count) > > > > > > { > > > > > > - unsigned int i = 0; > > > > > > - for (auto &ctrl : *ctrls) { > > > > > > - if (i == count) > > > > > > - break; > > > > > > - > > > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > > > > > - unsigned int id = ctrl.first; > > > > > > - ControlValue &value = ctrl.second; > > > > > > + for (unsigned int i = 0; i < count; i++) { > > > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > > > > > + const unsigned int id = v4l2Ctrl.id; > > > > > > + if (!ctrls->contains(id)) { > > > > > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > > > > > + << id; > > > > > > + return; > > > > > > + } > > > > > > > > > > > > - const auto iter = controls_.find(id); > > > > > > - switch (iter->first->type()) { > > > > > > + ControlValue value = ctrls->get(id); > > > > > > > > > > This is less efficient, as the function now runs with O(n^2) complexity. > > > > > > > > Can you explain me why the time complexity is O(n^2)? > > > > Since controls_ is based on std::unordered_map, find(), contains(), > > > > get() and set() should be O(1). > > > > So I think this is still O(n). > > I read that all these functions are "in worst case" linear to the > length of the input in complexity > > > > > > > You're right that it's not O(n^2) as we use an unordered map. > > > std::unordered_map::find() is "constant on average, worst case linear in > > > the size of the container". > > > > > > > > Given that updateControls() is private, why is requiring ctrls and > > > > > v4l2Ctrls to have the same order a problem ? The requirement should be > > > > > documented, but does it cause any issue ? > > > > > > > > I think the restriction is strange and unnecessary, and a caller might > > > > have to pre-process to keep that. > > > > Well, so far, the caller is only V4L2Device and we don't need anything > > > > to keep the rule. > > > > > > That was my point, it's a private function of the class :-) As all > > > callers currently guarantee the order, I'd defer this change until we > > > have a use case. > > > > > > > I forgot mentioning there is no guaranteed upon traversing std::unordered_map. > > https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c > > > > So I think as long as std::unordered_map is used, the original > > implementation is problematic? > > If you look at the callers, the v4l2Ctrls are filled in by iterating > on the ControlList (which is an unordered map). > > Regardless of how the ControlList is sorted, v4l2Ctrls will have the > same sorting order. There's a comment that explains that in > getControls(): > > /* > * Start by filling the ControlList. This can't be combined with filling > * v4l2Ctrls, as updateControls() relies on both containers having the > * same order, and the control list is based on a map, which is not > * sorted by insertion order. > */ > Thanks. I missed this comment. > I might have missed what issue you have encountered. > > I'm anyway not opposed to this change, as the ordering assumption is a > bit weird, even if it should be safe. > > Changing such a core feature would require some careful testing, and > if there's no actual reason to change it I would be cautious to do so > but I'm not opposed... > I actually have never faced any issue due to this. As a reader, this assumption is unnecessary and thus feels strange for me. Removing the assumption is simple enough I believe, so I hope this change makes sense to everyone. -Hiro > > > -Hiro > > > > > > > > + switch (value.type()) { > > > > > > case ControlTypeInteger64: > > > > > > - value.set<int64_t>(v4l2Ctrl->value64); > > > > > > + value.set<int64_t>(v4l2Ctrl.value64); > > > > > > break; > > > > > > > > > > > > case ControlTypeByte: > > > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > > * \todo To be changed when support for string controls > > > > > > * will be added. > > > > > > */ > > > > > > - value.set<int32_t>(v4l2Ctrl->value); > > > > > > + value.set<int32_t>(v4l2Ctrl.value); > > > > > > break; > > > > > > } > > > > > > > > > > > > - i++; > > > > > > + ctrls->set(id, value); > > > > > > } > > > > > > } > > > > > > > > > > > > -- > > > Regards, > > > > > > Laurent Pinchart > > _______________________________________________ > > libcamera-devel mailing list > > libcamera-devel@lists.libcamera.org > > https://lists.libcamera.org/listinfo/libcamera-devel
Hi Hiro, One more comment on the patch itself On Thu, Apr 22, 2021 at 11:14:59AM +0900, Hirokazu Honda wrote: > On Wed, Apr 21, 2021 at 9:36 PM Jacopo Mondi <jacopo@jmondi.org> wrote: > > > > Hi Hiro, > > > > On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote: > > > On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart > > > <laurent.pinchart@ideasonboard.com> wrote: > > > > > > > > Hi Hiro, > > > > > > > > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote: > > > > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote: > > > > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote: > > > > > > > The original updateControls() has the assumption that ctrls and > > > > > > > v4l2Ctrls lists in the same order. It is dependent on the caller > > > > > > > implementation though. This changes updateControls() > > > > > > > implementation so that it works without the assumption. > > > > > > > > > > > > > > Signed-off-by: Hirokazu Honda <hiroh@chromium.org> > > > > > > > --- > > > > > > > src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- > > > > > > > 1 file changed, 13 insertions(+), 13 deletions(-) > > > > > > > > > > > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp > > > > > > > index d4a9bb75..8fd79934 100644 > > > > > > > --- a/src/libcamera/v4l2_device.cpp > > > > > > > +++ b/src/libcamera/v4l2_device.cpp > > > > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > > > const struct v4l2_ext_control *v4l2Ctrls, > > > > > > > unsigned int count) > > > > > > > { > > > > > > > - unsigned int i = 0; > > > > > > > - for (auto &ctrl : *ctrls) { > > > > > > > - if (i == count) > > > > > > > - break; > > > > > > > - > > > > > > > - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; > > > > > > > - unsigned int id = ctrl.first; > > > > > > > - ControlValue &value = ctrl.second; > > > > > > > + for (unsigned int i = 0; i < count; i++) { > > > > > > > + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; > > > > > > > + const unsigned int id = v4l2Ctrl.id; > > > > > > > + if (!ctrls->contains(id)) { > > > > > > > + LOG(V4L2, Error) << "ControlList doesn't contain id: " > > > > > > > + << id; > > > > > > > + return; > > > > > > > + } This can't happen, as this is a private function and we control the callers > > > > > > > > > > > > > > - const auto iter = controls_.find(id); > > > > > > > - switch (iter->first->type()) { > > > > > > > + ControlValue value = ctrls->get(id); > > > > > > > > > > > > This is less efficient, as the function now runs with O(n^2) complexity. > > > > > > > > > > Can you explain me why the time complexity is O(n^2)? > > > > > Since controls_ is based on std::unordered_map, find(), contains(), > > > > > get() and set() should be O(1). > > > > > So I think this is still O(n). > > > > I read that all these functions are "in worst case" linear to the > > length of the input in complexity > > > > > > > > > > You're right that it's not O(n^2) as we use an unordered map. > > > > std::unordered_map::find() is "constant on average, worst case linear in > > > > the size of the container". > > > > > > > > > > Given that updateControls() is private, why is requiring ctrls and > > > > > > v4l2Ctrls to have the same order a problem ? The requirement should be > > > > > > documented, but does it cause any issue ? > > > > > > > > > > I think the restriction is strange and unnecessary, and a caller might > > > > > have to pre-process to keep that. > > > > > Well, so far, the caller is only V4L2Device and we don't need anything > > > > > to keep the rule. > > > > > > > > That was my point, it's a private function of the class :-) As all > > > > callers currently guarantee the order, I'd defer this change until we > > > > have a use case. > > > > > > > > > > I forgot mentioning there is no guaranteed upon traversing std::unordered_map. > > > https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c > > > > > > So I think as long as std::unordered_map is used, the original > > > implementation is problematic? > > > > If you look at the callers, the v4l2Ctrls are filled in by iterating > > on the ControlList (which is an unordered map). > > > > Regardless of how the ControlList is sorted, v4l2Ctrls will have the > > same sorting order. There's a comment that explains that in > > getControls(): > > > > /* > > * Start by filling the ControlList. This can't be combined with filling > > * v4l2Ctrls, as updateControls() relies on both containers having the > > * same order, and the control list is based on a map, which is not > > * sorted by insertion order. > > */ > > > > Thanks. I missed this comment. > > > I might have missed what issue you have encountered. > > > > I'm anyway not opposed to this change, as the ordering assumption is a > > bit weird, even if it should be safe. > > > > Changing such a core feature would require some careful testing, and > > if there's no actual reason to change it I would be cautious to do so > > but I'm not opposed... > > > > I actually have never faced any issue due to this. > As a reader, this assumption is unnecessary and thus feels strange for me. > Removing the assumption is simple enough I believe, so I hope this > change makes sense to everyone. > -Hiro > Makes sense, the caller should be updated too to remove the assumption too then, ideally removing the double for loop in getControls(). The test covers updateControls() enough that making sure they pass it's ok to consier this change safe. Thanks j > > > > > -Hiro > > > > > > > > > > + switch (value.type()) { > > > > > > > case ControlTypeInteger64: > > > > > > > - value.set<int64_t>(v4l2Ctrl->value64); > > > > > > > + value.set<int64_t>(v4l2Ctrl.value64); > > > > > > > break; > > > > > > > > > > > > > > case ControlTypeByte: > > > > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, > > > > > > > * \todo To be changed when support for string controls > > > > > > > * will be added. > > > > > > > */ > > > > > > > - value.set<int32_t>(v4l2Ctrl->value); > > > > > > > + value.set<int32_t>(v4l2Ctrl.value); > > > > > > > break; > > > > > > > } > > > > > > > > > > > > > > - i++; > > > > > > > + ctrls->set(id, value); > > > > > > > } > > > > > > > } > > > > > > > > > > > > > > > -- > > > > Regards, > > > > > > > > Laurent Pinchart > > > _______________________________________________ > > > libcamera-devel mailing list > > > libcamera-devel@lists.libcamera.org > > > https://lists.libcamera.org/listinfo/libcamera-devel
diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp index d4a9bb75..8fd79934 100644 --- a/src/libcamera/v4l2_device.cpp +++ b/src/libcamera/v4l2_device.cpp @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls, const struct v4l2_ext_control *v4l2Ctrls, unsigned int count) { - unsigned int i = 0; - for (auto &ctrl : *ctrls) { - if (i == count) - break; - - const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i]; - unsigned int id = ctrl.first; - ControlValue &value = ctrl.second; + for (unsigned int i = 0; i < count; i++) { + const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i]; + const unsigned int id = v4l2Ctrl.id; + if (!ctrls->contains(id)) { + LOG(V4L2, Error) << "ControlList doesn't contain id: " + << id; + return; + } - const auto iter = controls_.find(id); - switch (iter->first->type()) { + ControlValue value = ctrls->get(id); + switch (value.type()) { case ControlTypeInteger64: - value.set<int64_t>(v4l2Ctrl->value64); + value.set<int64_t>(v4l2Ctrl.value64); break; case ControlTypeByte: @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls, * \todo To be changed when support for string controls * will be added. */ - value.set<int32_t>(v4l2Ctrl->value); + value.set<int32_t>(v4l2Ctrl.value); break; } - i++; + ctrls->set(id, value); } }
The original updateControls() has the assumption that ctrls and v4l2Ctrls lists in the same order. It is dependent on the caller implementation though. This changes updateControls() implementation so that it works without the assumption. Signed-off-by: Hirokazu Honda <hiroh@chromium.org> --- src/libcamera/v4l2_device.cpp | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-)