Allow pointer compare instead of string compare with keys, group and item

[Daniel Schürmann]

If we extend the Key Api in a way, that we have every group and key string only one time in memory, we could switch to pointer compare instead of string or hash compare at many places inside Mixxx. Or we can remove some workarounds, that where introduced in hot paths to avoid the string compare.

We can just rename the "const char* group" to "GroupHandle group" and introduce some conversion functions.
The parts are already in place
eg:
const char* LegacySkinParser::safeChannelString(QString channelStr);

[RJ Skerry-Ryan (rryan)]

Thanks for filing this but before spending any time on this bug please
first present data that this is a performance issue. I don't believe that
doing QMap lookups or string comparisons produce a measurable impact the
way we are using them. Of course we should not do them in a per-sample loop
but a per-group loop is likely fine. I'm happy to be proven otherwise but I
won't accept micro-optimization patches that make things more complicated
with no real benefit.

For sure, we should benchmark QList linear scans versus QMap and QHash
(based on the small number of groups we use the general wisdom is we should
be using QMap over QHash). The small number of groups may make the n^2
approach faster in practice than a more complicated constant time or log n
structure.

On Saturday, February 22, 2014 10:55:39 PM, Daniel Schürmann <
<email address hidden>> wrote:

Public bug reported:

If we extend the Key Api in a way, that we have every group and key
string only one time in memory, we could switch to pointer compare
instead of string or hash compare at many places inside Mixxx. Or we can
remove some workarounds, that where introduced in hot paths to avoid the
string compare.

We can just rename the "const char* group" to "GroupHandle group" and
introduce some conversion functions.
The parts are already in place
eg:
const char* LegacySkinParser::safeChannelString(QString channelStr);

** Affects: mixxx
     Importance: Undecided
         Status: New

--
You received this bug notification because you are a member of Mixxx
Development Team, which is subscribed to Mixxx.
https://bugs.launchpad.net/bugs/1283471

Title:
  Allow pointer compare instead of string compare with keys, group and
  item

To manage notifications about this bug go to:
https://bugs.launchpad.net/mixxx/+bug/1283471/+subscriptions

[Owen Williams (ywwg)]

Due to feature freeze, this work should wait until after the 1.12 release.

[RJ Skerry-Ryan (rryan)]

> I'm happy to be proven otherwise

Well, looks like I've proven myself wrong! I've been doing some profiling.

Playing a single track with no effects active the EngineEffectChain::m_groupStatus map's operator[] method accounts for 14% of time spent in EngineMaster::process. The bulk of time spent is in QString::operator<.

Switching to a QHash drops this to 5.9% but just shifts the bulk of the work into qHash(QString).
Switching to searching a QLinkedList drops this to 4% and the bulk of the work is in QString::operator==.

If we solved this bug by giving every GroupHandle an incremental integer (starting at zero) then we could probably use a QVarLengthArray and index directly. I would guess the time spent doing lookups would be negligible in that case.

[Daniel Schürmann (daschuer)]

Intesting!

Do you know the X11 Atom API?

http://tronche.com/gui/x/xlib/window-information/XInternAtom.html
used in:
/src/gui/kernel/qdnd_x11.cpp

We may do it quite similar.

This way we can easily change
new EngineMicrophone(group, m_pEffectsManager);

by
new EngineMicrophone(MixxxAtom(group), m_pEffectsManager);

And work inside with the Atom IDs

MIxxxAtom() will look like that

typedef AtomID QString*

AtomID MixxxAtom(QString name) {
   AtomID = m_IDHash[name];
   if (!AtomID) {
      AtomID = new QString(name);
      m_IDHash[name] = AtomID
   }
  return AtomID;
}

What do you think?

[RJ Skerry-Ryan (rryan)]

One downside to the example you gave above is that the pointers are only useful for equality. They don't help us get rid of expensive associative data structures like QMap and QHash -- they just speed up the comparisons that those structures do (qHash of pointer instead of string for QHash, operator< for integer instead of string for QMap). We could drop the cost of these associative lookups by an order of magnitude if we were able to do direct memory lookups by the handle.

An atom that is defined as an integer that starts at 0 and increases would allow us to use a QVarLengthArray with a more-than-expected-channels pre-allocation. Then we could have (group -> data) associative containers with essentially no cost.

WDYT?

[RJ Skerry-Ryan (rryan)]

Oh yea -- integers -> no garbage to clean up :).

[Daniel Schürmann (daschuer)]

We have these Hashes that will benefit:
QHash<QString, GroupStateHolder> GroupEffectProcessor::m_groupState;
QHash<QString, EffectRackPointer> EffectChainManager::m_effectRacksByGroup;
QHash<QString, EffectChainSlotPointer> PerGroupRack::m_groupToChainSlot;
QHash<ConfigKey, QWeakPointer<ControlDoublePrivate> > ControlDoublePrivate::s_qCOHash;
QHash<ConfigKey, ConfigKey> ControlDoublePrivate::s_qCOAliasHash;
QHash<ConfigKey, QString> m_descriptionsByKey;
QHash<ConfigKey, QString> m_titlesByKey;

You are right, it is in most cases the group string, that would make the difference.
We have already a hard Limit of 32 Groups inside the EngineMaster
So we can Replace the Group String by an Index of 0 .. 31 in most cases.

The pointer version has a benefit that we can convert them back to QStrings with no costs,
but we do not do this in time critical paths.

We can't get rid of the strings, since we need them in skins and midi scripts.
A QString Lookup will still require a Hash
We need String Lookup for creating ControObjectsSlaves.
Separating the Group string will be de-optimization.

Conclusion: lets introduce a Group Index!

@rryan: Can you please have a look at
https://github.com/mixxxdj/mixxx/pull/474
I includes some refactoring we can base this on.

[Swiftb0y (swiftb0y)]

Mixxx now uses GitHub for bug tracking. This bug has been migrated to:
https://github.com/mixxxdj/mixxx/issues/7323