Hi RJ,
I've been testing this patch since you sent it to see if it had a
performance impact. As far as I can tell, the increased CPU utilization
in the getControl() calls is negligible. Regardless, correctness IS
more important than speed, so please apply your patch to trunk. :)
Thanks,
Albert
On Wed, 2008-07-02 at 23:41 -0400, Russell Ryan wrote:
> Hey all, as discussed in my previous email, here's a patch to some of
> the issues we've seen in ControlObject::getControl.
>
> One improvement is moving from Q3PtrList to QHash, and using ConfigKey
> as the key into this hashset. The hash function I picked for ConfigKey
> is composed of QString's built in hash function and xor:
>
> for hash(configkey), the hash value is QStringHash(group) XOR
> QStringHash(key).
>
> Anyone with experience with hash functions, please tell me if that's
> reasonable :)
>
>
> getControl used to be O(n) in the number of ControlObjects that exist,
> and using the hash, we can now expect O(1) performance.
>
> In this patch, I've gone for correctness over speed. The ControlObject
> hash is protected with a mutex for all operations -- add, remove, and
> lookup. We have too many mysterious bugs to allow race condition between
> a lookup and an append or remove.
>
> Also, in looking at usage patterns for getControl, given that it uses a
> lock now, that means you should cache its output wherever possible. If
> you are writing a class, instead of using getControl each time you need
> the control, look it up when the class is instantiated and store it in a
> member variable instead of doing : getControl(somekey)->get() each
> time you want the value.
>
>
> Let me know if you have any comments. This should eliminate the race
> conditions we were seeing the other night. If everyone thinks it looks
> good I'll push it into trunk, and we can see if this helps any of our
> open bugs. (hey, we can be optimistic right? :) )
>
>
> Cheers,
> RJ
> plain text document attachment (control_object_hash_patch)
> Index: mixxx/src/controlobject.cpp
> ===================================================================
> --- mixxx/src/controlobject.cpp (revision 2120)
> +++ mixxx/src/controlobject.cpp (working copy)
> @@ -17,13 +17,14 @@
>
> #include <qwidget.h>
> #include <QtDebug>
> -//Added by qt3to4:
> -#include <Q3PtrList>
> +#include <QHash>
> #include "controlobject.h"
> #include "controlevent.h"
>
> // Static member variable definition
> -Q3PtrList<ControlObject> ControlObject::m_sqList;
> +QHash<ConfigKey,ControlObject*> ControlObject::m_sqCOHash;
> +QMutex ControlObject::m_sqCOHashMutex;
> +
> QMutex ControlObject::m_sqQueueMutexMidi;
> QMutex ControlObject::m_sqQueueMutexThread;
> QMutex ControlObject::m_sqQueueMutexChanges;
> @@ -39,12 +40,16 @@
> {
> m_dValue = 0.;
> m_Key = key;
> - m_sqList.append(this);
> + m_sqCOHashMutex.lock();
> + m_sqCOHash.insert(key,this);
> + m_sqCOHashMutex.unlock();
> }
>
> ControlObject::~ControlObject()
> {
> - m_sqList.remove(this);
> + m_sqCOHashMutex.lock();
> + m_sqCOHash.remove(m_Key);
> + m_sqCOHashMutex.unlock();
> }
>
> bool ControlObject::connectControls(ConfigKey src, ConfigKey dest)
> @@ -104,16 +109,17 @@
>
> ControlObject * ControlObject::getControl(ConfigKey key)
> {
> - // qDebug() << "trying to get group" << key.group << "item" << key.item;
> + //qDebug() << "ControlObject::getControl for (" << key.group << "," <<
> key.item << ")";
> + m_sqCOHashMutex.lock();
> + if(m_sqCOHash.contains(key)) {
> + ControlObject *co = m_sqCOHash[key];
> + m_sqCOHashMutex.unlock();
> + return co;
> + }
> + m_sqCOHashMutex.unlock();
>
> - // Loop through the list of ConfigObjects to find one matching key
> - ControlObject * c;
> - for (c=m_sqList.first(); c; c=m_sqList.next())
> - {
> - if (c->getKey().group == key.group && c->getKey().item == key.item)
> - return c;
> - }
> - return 0;
> + qDebug() << "ControlObject::getControl returning NULL for (" <<
> key.group << "," << key.item << ")";
> + return NULL;
> }
>
> void ControlObject::queueFromThread(double dValue, ControlObjectThread *
> pControlObjectThread)
> Index: mixxx/src/controlobject.h
> ===================================================================
> --- mixxx/src/controlobject.h (revision 2120)
> +++ mixxx/src/controlobject.h (working copy)
> @@ -124,8 +124,10 @@
> private:
> /** List of associated proxy objects */
> Q3PtrList<ControlObjectThread> m_qProxyList;
> - /** List of ControlObject instantiations */
> - static Q3PtrList<ControlObject> m_sqList;
> + /** Hash of ControlObject instantiations */
> + static QHash<ConfigKey,ControlObject*> m_sqCOHash;
> + /** Mutex guarding access to the ControlObject hash **/
> + static QMutex m_sqCOHashMutex;
> /** Mutex protecting access to the queues */
> static QMutex m_sqQueueMutexMidi, m_sqQueueMutexThread,
> m_sqQueueMutexChanges;
> /** Queue holding control changes from MIDI */
> Index: mixxx/src/configobject.h
> ===================================================================
> --- mixxx/src/configobject.h (revision 2120)
> +++ mixxx/src/configobject.h (working copy)
> @@ -26,6 +26,7 @@
> #include <qkeysequence.h>
> #include <qdom.h>
> #include <qmap.h>
> +#include <QHash>
>
> typedef enum {
> MIDI_EMPTY = 0,
> @@ -58,10 +59,20 @@
> public:
> ConfigKey();
> ConfigKey(QString g, QString i);
> -
> +
> QString group, item;
> };
>
> +/* comparison function for ConfigKeys. Used by a QHash in ControlObject */
> +inline bool operator==(const ConfigKey &c1, const ConfigKey &c2) {
> + return c1.group == c2.group && c1.item == c2.item;
> +}
> +
> +/* QHash hash function for ConfigKey objects. */
> +inline uint qHash(const ConfigKey &key) {
> + return qHash(key.group) ^ qHash(key.item);
> +}
> +
> /*
> The value corresponding to a key. The basic value is a string, but can be
> subclassed to more specific needs.
> -------------------------------------------------------------------------
> Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
> Studies have shown that voting for your favorite open source project,
> along with a healthy diet, reduces your potential for chronic lameness
> and boredom. Vote Now at http://www.sourceforge.net/community/cca08
> _______________________________________________ Mixxx-devel mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/mixxx-devel
-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
Mixxx-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/mixxx-devel
