Created attachment 19836 [details]
Speeds up playlist loading by adding a URL index.

Hello,
I have to say I cannot reproduce this.  I have tested adding songs without your patch (with everything in the playlist, and trying to add 270 songs).  I do not see any speedups with your patch, it seems fast without.

Could you please provide some more information on what problem this fixes?

Thank you

I have smart playlist of ~5000 items, and one ~9700 items, which I use
to switch between sets of genres. The progress bar slows down
significantly during the loading of the playlists, pointing to an
O(N^2) operation. The whole thing lasts much longer without the patch
than with the patch.

Using valgrind, I have tracked the slowdown to the duplicate checking
-- most of the time during playlist loading was being spent there.

Regards,
Ovy

On 1 Mar 2007 22:27:49 -0000, Dan Meltzer
<hydrogen@notyetimplemented.com> wrote:
[bugs.kde.org quoted mail]

SVN commit 639658 by dmeltzer:

Eliminate Quadratic behavior in the duplicate checking code.
Patch by Ovy <ovy@alum.mit.edu>
BUG: 142255


 M  +2 -0      ChangeLog  
 M  +0 -5      src/atomicstring.cpp  
 M  +6 -1      src/atomicstring.h  
 M  +28 -47    src/playlist.cpp  
 M  +72 -12    src/playlist.h  
 M  +18 -5     src/playlistitem.cpp  
 M  +1 -11     src/playlistloader.cpp  
 M  +1 -1      src/playlistloader.h  
 M  +6 -6      src/playlistwindow.h  


--- branches/stable/extragear/multimedia/amarok/ChangeLog #639657:639658
@@ -11,6 +11,8 @@
   BUGFIXES:
     * Fix detection of vfat devices on FreeBSD. (BR 141614)
     * Right-click on volume slider would change the volume. (BR 141672)
+    * Fix Quadratic loading in Playlists (BR 142255) Patch by Ovy
+    <ovy@alum.mit.edu>
 
 
 VERSION 1.4.5
--- branches/stable/extragear/multimedia/amarok/src/atomicstring.cpp #639657:639658
@@ -183,11 +183,6 @@
     return *this;
 }
 
-bool AtomicString::operator==( const AtomicString &other ) const
-{
-    return m_string == other.m_string;
-}
-
 // needs to be called holding the lock
 inline void AtomicString::deref( Data *s )
 {
--- branches/stable/extragear/multimedia/amarok/src/atomicstring.h #639657:639658
@@ -94,8 +94,13 @@
      * This operation takes constant time.
      * @return whether this string and \p string are equivalent
      */
-    bool operator==( const AtomicString &other ) const;
+    bool operator==( const AtomicString &other ) const { return m_string == other.m_string; }
 
+
+    bool operator<( const AtomicString &other ) const { return m_string < other.m_string; }
+
+//     bool operator!=( const AtomicString &other ) const { return m_string != other.m_string; }
+
     /**
      * Returns a reference to this string, avoiding copies if possible.
      *
--- branches/stable/extragear/multimedia/amarok/src/playlist.cpp #639657:639658
@@ -196,6 +196,8 @@
         , m_oldRepeat( 0 )
         , m_playlistName( i18n( "Untitled" ) )
         , m_proposeOverwriting( false )
+        , m_urlIndex( &PlaylistItem::url )
+         
 {
     s_instance = this;
 
@@ -444,7 +446,7 @@
 }
 
 void
-Playlist::insertMedia( KURL::List list, int options )
+Playlist::insertMedia( const KURL::List &list, int options )
 {
     if( list.isEmpty() ) {
         Amarok::StatusBar::instance()->shortMessage( i18n("Attempted to insert nothing into playlist.") );
@@ -463,67 +465,47 @@
 
     PlaylistItem *after = lastItem();
 
-    if( options & Queue )
-    {
-        KURL::List addMe = list;
-        KURL::List::Iterator jt;
+    KURL::List addMe;
+    QPtrList<PlaylistItem> alreadyHave;
 
-        // add any songs not in the playlist to it.
-        for( MyIt it( this, MyIt::All ); *it; ++it ) {
-            jt = addMe.find( (*it)->url() );
+    // Filter out duplicates
+    foreachType( KURL::List, list ) {
+        PlaylistItem *item = m_urlIndex.getFirst( *it );
+        if ( item )
+            alreadyHave.append( item );
+        else 
+            addMe.append( *it );
+    }
 
-            if ( jt != addMe.end() ) {
-                addMe.remove( jt ); //don't want to add a track which is already present in the playlist
-            }
-        }
-
+    if( options & Queue )
+    {
         if ( addMe.isEmpty() ) // all songs to be queued are already in the playlist
         {
-            // find the songs and queue them.
-            for (MyIt it( this, MyIt::All ); *it; ++it ) {
-                jt = list.find( (*it)->url() );
-
-                if ( jt != list.end() )
-                {
-                    queue( *it, false, false );
-                    list.remove( jt );
-                }
-            }
+            // queue all the songs
+            foreachType( QPtrList<PlaylistItem>, alreadyHave )
+                queue( *it, false, false );
+            return;
         } else {
             // We add the track after the last track on queue, or after current if the queue is empty
             after = m_nextTracks.isEmpty() ? currentTrack() : m_nextTracks.getLast();
             // If there's no tracks on the queue, and there's no current track, fall back to the last item
             if ( !after )
                 after = lastItem();
-
-            insertMediaInternal( addMe, after, options );
         }
-        return;
-
     }
     else if( options & Unique ) {
-        //passing by value is quick for QValueLists, though it is slow
-        //if we change the list, but this is unlikely
-        KURL::List::Iterator jt;
-        int alreadyOnPlaylist = 0;
-        for( MyIt it( this, MyIt::All ); *it; ++it ) {
-            jt = list.find( (*it)->url() );
-
-            if ( jt != list.end() ) {
-                if ( directPlay && jt == list.begin() ) {
-                    directPlay = false;
-                    activate( *it );
-                }
-
-                list.remove( jt );
-                alreadyOnPlaylist++;
-            }
-        }
+        int alreadyOnPlaylist = alreadyHave.count();
         if ( alreadyOnPlaylist )
-            Amarok::StatusBar::instance()->shortMessage( i18n("One track was already in the playlist, so it was not added.", "%n tracks were already in the playlist, so they were not added.", alreadyOnPlaylist ) );
+        {
+            if (directPlay) activate( alreadyHave.getFirst() );
+            Amarok::StatusBar::instance()->shortMessage(
+                i18n("One track was already in the playlist, so it was not added.",
+                     "%n tracks were already in the playlist, so they were not added.",
+                     alreadyOnPlaylist ) );
+        }
     }
 
-    insertMediaInternal( list, after, options );
+    insertMediaInternal( addMe, after, options );
 }
 
 void
@@ -4707,7 +4689,6 @@
     // Playlist::unlock();
 }
 
-
 #include <kactivelabel.h>
 #include <kdialog.h>
 #include <kpushbutton.h>
--- branches/stable/extragear/multimedia/amarok/src/playlist.h #639657:639658
@@ -41,7 +41,6 @@
 
 class KAction;
 class KActionCollection;
-class MyAtomicString;
 class PlaylistItem;
 class PlaylistEntry;
 class PlaylistLoader;
@@ -70,6 +69,13 @@
  */
 
 
+// template <class FieldType>
+// AtomicString Index<FieldType>::fieldString(const FieldType &field) { return AtomicString(field); }
+
+// template<>
+// AtomicString Index<KURL>::fieldString(const KURL &field);
+
+
 class Playlist : private KListView, public EngineObserver, public Amarok::ToolTipClient
 {
         Q_OBJECT
@@ -100,7 +106,7 @@
         /** Add media to the playlist
          *  @param options you can OR these together, see the enum
          *  @param sql     Sql program to execute */
-        LIBAMAROK_EXPORT void insertMedia( KURL::List, int options = Append );
+        LIBAMAROK_EXPORT void insertMedia( const KURL::List &, int options = Append );
         void insertMediaSql( const QString& sql, int options = Append );
 
         // Dynamic mode functions
@@ -341,8 +347,8 @@
         void removeFromPreviousTracks( PlaylistItem *item = 0 );
         void removeFromPreviousAlbums( PlaylistAlbum *album = 0 );
 
-        typedef QMap<MyAtomicString, PlaylistAlbum*> AlbumMap;
-        typedef QMap<MyAtomicString, AlbumMap> ArtistAlbumMap;
+        typedef QMap<AtomicString, PlaylistAlbum*> AlbumMap;
+        typedef QMap<AtomicString, AlbumMap> ArtistAlbumMap;
         ArtistAlbumMap m_albums;
         uint m_startupTime_t; //QDateTime::currentDateTime().toTime_t as of startup
         uint m_oldestTime_t; //the createdate of the oldest song in the collection
@@ -421,15 +427,61 @@
 
         QString m_playlistName;
         bool m_proposeOverwriting;
-};
 
-class MyAtomicString: public AtomicString
-{
-public:
-    MyAtomicString() { }
-    MyAtomicString(const QString &string): AtomicString( string ) { }
-    MyAtomicString(const AtomicString &other): AtomicString( other ) { }
-    bool operator<(const AtomicString &other) const { return ptr() < other.ptr(); }
+        // indexing stuff
+        // An index of playlist items by some field. The index is backed by AtomicStrings, to avoid
+        // duplication thread-safely. 
+        template <class FieldType>
+        class Index : private QMap<AtomicString, QPtrList<PlaylistItem> >
+        {
+          public:
+            // constructors take the PlaylistItem getter to index by
+            Index( FieldType (PlaylistItem::*getter)( ) const)
+            : m_getter( getter ), m_useGetter( true ) { };
+            Index( const FieldType &(PlaylistItem::*refGetter)() const)
+                : m_refGetter( refGetter ), m_useGetter( false ) { };
+        
+            // we specialize this method, below, for KURLs
+            AtomicString fieldString( const FieldType &field) { return AtomicString( field ); }
+            
+            AtomicString keyOf( const PlaylistItem &item) {
+                return m_useGetter ? fieldString( ( item.*m_getter ) () )
+                    : fieldString( ( item.*m_refGetter ) () );
+            }
+
+            bool contains( const FieldType &key ) { return contains( fieldString( key ) ); }
+            
+            // Just first match, or NULL
+            PlaylistItem *getFirst( const FieldType &field )  {
+                Iterator it = find( fieldString( field ) );
+                return it == end() || it.data().isEmpty() ? 0 : it.data().getFirst();
+            }
+
+            void add( PlaylistItem *item ) {
+                QPtrList<PlaylistItem> &row = operator[]( keyOf( *item ) );  // adds one if needed
+                if ( !row.containsRef(item) ) row.append( item );
+            }
+
+            void remove( PlaylistItem *item ) {
+                Iterator it = find( keyOf( *item ) );
+                if (it != end()) {
+                    while ( it.data().removeRef( item ) ) { };
+                    if ( it.data().isEmpty() ) erase( it );
+                }
+            }
+                           
+          private:
+            FieldType (PlaylistItem::*m_getter) () const;
+            const FieldType &(PlaylistItem::*m_refGetter) () const;
+            bool m_useGetter;       // because a valid *member can be zero in C++
+        };
+    
+        Index<KURL> m_urlIndex;
+        // TODO: we can convert m_unique to this, to remove some code and for uniformity and thread
+        //  safety
+        // TODO: we should just store the url() as AtomicString, it will save headaches (e.g. at least a
+        //  crash with multicore enabled traces back to KURL refcounting)
+        //Index<QString> m_uniqueIndex;
 };
 
 class PlaylistAlbum
@@ -484,4 +536,12 @@
 
 };
 
+// Specialization of Index::fieldString for URLs
+template<>
+inline AtomicString Playlist::Index<KURL>::fieldString( const KURL &url )
+{
+    return AtomicString( url.url() );
+}
+
 #endif //AMAROK_PLAYLIST_H
+
--- branches/stable/extragear/multimedia/amarok/src/playlistitem.cpp #639657:639658
@@ -69,9 +69,11 @@
 {
     setDragEnabled( true );
 
+    Playlist::instance()->m_urlIndex.add( this );
     if( !uniqueId().isEmpty() )
         Playlist::instance()->addToUniqueMap( uniqueId(), this );
 
+
     refAlbum();
 
     incrementCounts();
@@ -99,6 +101,9 @@
         listView()->m_hoveredRating = 0;
 
     Playlist::instance()->removeFromUniqueMap( uniqueId(), this );
+    Playlist::instance()->m_urlIndex.remove(this);
+
+
 }
 
 
@@ -141,13 +146,15 @@
 
 void PlaylistItem::aboutToChange( const QValueList<int> &columns )
 {
-    bool totals = false, ref = false, length = false;
+    bool totals = false, ref = false, length = false, url = false;
     for( int i = 0, n = columns.count(); i < n; ++i )
         switch( columns[i] )
         {
 	    case Length: length = true; break;
             case Artist: case Album: ref = true; //note, no breaks
-            case Track: case Rating: case Score: case LastPlayed: totals = true;
+            case Track: case Rating: case Score: case LastPlayed:
+                totals = true; break;
+            case Filename: case Directory: url = true; break;
         }
     if ( length )
         decrementLengths();
@@ -155,12 +162,14 @@
         decrementTotals();
     if( ref )
         derefAlbum();
+    if ( url )
+        Playlist::instance()->m_urlIndex.remove(this);
 }
 
 void PlaylistItem::reactToChanges( const QValueList<int> &columns )
 {
     MetaBundle::reactToChanges(columns);
-    bool totals = false, ref = false, length = false;
+    bool totals = false, ref = false, length = false, url = false;
     for( int i = 0, n = columns.count(); i < n; ++i )
       {
         if( columns[i] == Mood )
@@ -173,10 +182,14 @@
         switch( columns[i] )
         {
             case Artist: case Album: ref = true; //note, no breaks
-            case Track: case Rating: case Score: case LastPlayed: totals = true;
-            default: updateColumn( columns[i] );
+            case Track: case Rating: case Score: case LastPlayed:
+                totals = true; break;
+            case Filename: case Directory: url = true;
         }
+        updateColumn( columns[i] );
       }
+    if ( url )
+        Playlist::instance()->m_urlIndex.add(this);
     if( ref )
         refAlbum();
     if( totals )
--- branches/stable/extragear/multimedia/amarok/src/playlistloader.cpp #639657:639658
@@ -236,22 +236,12 @@
     case 1000:
         foreachType( BundleList, e->bundles )
         {
-            //passing by value is quick for QValueLists, though it is slow
-            //if we change the list, but this is unlikely
-            KURL::List::Iterator jt;
             int alreadyOnPlaylist = 0;
 
             PlaylistItem *item = 0;
             if( m_options & (Playlist::Unique | Playlist::Queue) )
             {
-                for( PlaylistIterator jt( Playlist::instance(), PlaylistIterator::All ); *jt; ++jt )
-                {
-                    if( (*jt)->url() == (*it).url() )
-                    {
-                        item = *jt;
-                        break;
-                    }
-                }
+                item = Playlist::instance()->m_urlIndex.getFirst( (*it).url() );
             }
 
             if( item )
--- branches/stable/extragear/multimedia/amarok/src/playlistloader.h #639657:639658
@@ -108,7 +108,7 @@
     UrlLoader( const KURL::List&, QListViewItem*, int options = 0 );
    ~UrlLoader();
 
-    static const uint OPTIMUM_BUNDLE_COUNT = 50;
+    static const uint OPTIMUM_BUNDLE_COUNT = 200;
 
 signals:
     void queueChanged( const PLItemList &, const PLItemList & );
--- branches/stable/extragear/multimedia/amarok/src/playlistwindow.h #639657:639658
@@ -125,11 +125,11 @@
 {
     Q_OBJECT
     public:
-        DynamicTitle(QWidget* parent);
-        void setTitle(const QString& newTitle);
+        DynamicTitle( QWidget* parent );
+        void setTitle( const QString& newTitle );
 
     protected:
-        virtual void paintEvent(QPaintEvent* e);
+        virtual void paintEvent( QPaintEvent* e );
 
     private:
         static const int s_curveWidth = 5;
@@ -142,12 +142,12 @@
 {
     Q_OBJECT
     public:
-        DynamicBar(QWidget* parent);
+        DynamicBar( QWidget* parent );
         void init();
 
     public slots:
-        void slotNewDynamicMode(const DynamicMode* mode);
-        void changeTitle(const QString& title);
+        void slotNewDynamicMode( const DynamicMode* mode );
+        void changeTitle( const QString& title );
 
     private:
         DynamicTitle* m_titleWidget;