[libcamera-devel] [PATCH v5 01/17] libcamera: controls: Add a function to merge two control lists
Hirokazu Honda
hiroh at chromium.org
Thu May 6 10:08:11 CEST 2021
Hi Jacopo,
On Thu, May 6, 2021 at 4:44 PM Jacopo Mondi <jacopo at jmondi.org> wrote:
> Hi Hiro,
>
> On Thu, May 06, 2021 at 01:58:34PM +0900, Hirokazu Honda wrote:
> > On Tue, May 4, 2021 at 5:11 PM Kieran Bingham <
> > kieran.bingham at ideasonboard.com> wrote:
> >
> > > Hi Jacopo,
> > >
> > > On 03/05/2021 11:41, Jacopo Mondi wrote:
> > > > From: Laurent Pinchart <laurent.pinchart at ideasonboard.com>
> > > >
> > > > Add a new ControlList::merge() function to merge two control lists by
> > > > copying in the values in the list passed as parameters.
> > > >
> > > > This can be used by pipeline handlers to merge metadata they populate
> > > > with metadata received from an IPA.
> > > >
> > > > Signed-off-by: Laurent Pinchart <laurent.pinchart at ideasonboard.com>
> > > > [reimplement the function by not using std::unordered_map::merge()]
> > > > Signed-off-by: Jacopo Mondi <jacopo at jmondi.org>
> > >
> > > With the cost/const fixed
> > >
> > > Reviewed-by: Kieran Bingham <kieran.bingham at ideasonboard.com>
> > >
> > > > ---
> > > > include/libcamera/controls.h | 2 ++
> > > > src/libcamera/controls.cpp | 30 ++++++++++++++++++++++++++++++
> > > > 2 files changed, 32 insertions(+)
> > > >
> > > > diff --git a/include/libcamera/controls.h
> b/include/libcamera/controls.h
> > > > index 1a5690a5ccbe..1c9b37e617bc 100644
> > > > --- a/include/libcamera/controls.h
> > > > +++ b/include/libcamera/controls.h
> > > > @@ -363,7 +363,9 @@ public:
> > > >
> > > > bool empty() const { return controls_.empty(); }
> > > > std::size_t size() const { return controls_.size(); }
> > > > +
> > > > void clear() { controls_.clear(); }
> > > > + void merge(const ControlList &source);
> > > >
> > > > bool contains(const ControlId &id) const;
> > > > bool contains(unsigned int id) const;
> > > > diff --git a/src/libcamera/controls.cpp b/src/libcamera/controls.cpp
> > > > index c58ed3946f3b..d8f104e3734b 100644
> > > > --- a/src/libcamera/controls.cpp
> > > > +++ b/src/libcamera/controls.cpp
> > > > @@ -874,6 +874,36 @@ ControlList::ControlList(const ControlInfoMap
> > > &infoMap, ControlValidator *valida
> > > > * \brief Removes all controls from the list
> > > > */
> > > >
> > > > +/**
> > > > + * \brief Merge the \a source into the ControlList
> > > > + * \param[in] source The ControlList to merge into this object
> > > > + *
> > > > + * Merging two control lists copies elements from the \a source and
> > > inserts
> > > > + * them in *this. If the \a source contains elements whose key is
> > > already
> > > > + * present in *this, then those elements are not overwritten.
> > > > + *
> > > > + * Only control lists created from the same ControlIdMap or
> > > ControlInfoMap may
> > > > + * be merged. Attempting to do otherwise results in undefined
> behaviour.
> > > > + *
> > > > + * \todo Reimplement or implement an overloaded version which
> > > internally uses
> > > > + * std::unordered_map::merge() and accepts a non-cost argument.
> > > > + */
> > > > +void ControlList::merge(const ControlList &source)
> > > > +{
> > > > + ASSERT(idmap_ == source.idmap_);
> > >
> >
> > Comparing std::unordered_map is O(NlogN) although the following for-loop
> is
> > O(M), where N is the size of idmap_ and M is the size of source.
> > Would you consider if this is worth doing?
>
> Not sure I got this. Is your concern due to the idmap comparison ? Do
> you wonder if it is necessary ?
>
> It seems to me if we skip the comparison, things might seem to work
> well, as the control values mapped to ids are stored in controls_ not
> in idmap_.
>
> Thing is, if you construct two control lists from two different
> controls maps you have a risk of id collision, in two different
> maps the same ControlId can be mapped to a different unsigned int, or
> the other way around, two different ControlId can be mapped to the
> same numeric identifier.
>
> How likely is this to happen at the current development state in
> mainline libcamera ? Close to 0 I would say.
>
> However we should consider downstream implementation, which might use
> custom controls and control maps, especially in IPA. They could be
> tempted to mix them with lists constructed with the canonical
> controls::controls and if they're not particularly careful bad things
> can happen and can be quite difficult to debug.
>
> Considering the usual length of the control lists we deal with, I
> would say this check is worth it, but maybe I'm being paranoid and we
> can safely skip it.
>
> Or there might be better way to handle this, like
>
> for (const auto &ctrl : source) {
> if (idmap_[ctrl.first] != source.idmap_[ctrl.first])
> /* Error out ludly */
>
>
> }
>
> Although operator[] on an unordered map is linear in complexity in the
> worst case, so we would get a O(NM) complexity, which is slightly
> better than O(NlogNM). We're really talking details here, as with
> lists of up to a few tens of items, I don't think the difference is
> anyway relevant, but I appreciate the concern on staying as efficient
> as we can...
>
>
I missed the time complexity of std::unordered_map.
Comparing std::unordered_map is O(NlogN) although the following for-loop is
O(M), where N is the size of idmap_ and M is the size of source.
This should be O(N) and O(M), respectively.
So the original code is better than your proposal one.
>
> >
> > > > +
> > > > + for (const auto &ctrl : source) {
> > > > + if (contains(ctrl.first)) {
> > > > + const ControlId *id = idmap_->at(ctrl.first);
> > > > + LOG(Controls, Warning)
> > >
> >
> > I wonder if this is worth Warning. Debug seems to be natural for me.
> > Could you explain the reason?
>
> Good question, I went for Warning because I think this is a condition
> that should not happen, as an attempt to overwrite an existing control
> through merging is suspicious and most probably not desired ? I
> refrained from making this an error because it might be intentional,
> but to me it's a condition that developers (mostly pipeline
> developers) should be aware without going through the extensive Debug
> log. As Warnings are less frequent, but ordinarily masked, I considered
> this the right level. I can happily change this is if other debug
> levels are considered better.
>
>
Ack.
Reviewed-by: Hirokazu Honda <hiroh at chromium.org>
> Thanks
> j
>
> >
> > Thanks,
> > -Hiro
> >
> > > > + << "Control " << id->name() << " not
> > > overwritten";
> > > > + continue;
> > > > + }
> > > > +
> > > > + set(ctrl.first, ctrl.second);
> > > > + }
> > > > +}
> > > > +
> > > > /**
> > > > * \brief Check if the list contains a control with the specified
> \a id
> > > > * \param[in] id The control ID
> > > >
> > >
> > > --
> > > Regards
> > > --
> > > Kieran
> > > _______________________________________________
> > > libcamera-devel mailing list
> > > libcamera-devel at lists.libcamera.org
> > > https://lists.libcamera.org/listinfo/libcamera-devel
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.libcamera.org/pipermail/libcamera-devel/attachments/20210506/c56eba09/attachment-0001.htm>
More information about the libcamera-devel
mailing list