Bug 72831 - File Groups performance bad in some cases
Summary: File Groups performance bad in some cases
Status: RESOLVED FIXED
Alias: None
Product: kdevelop
Classification: Applications
Component: file groups (show other bugs)
Version: git master
Platform: Unlisted Binaries Linux
: NOR normal
Target Milestone: ---
Assignee: KDevelop Developers
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2004-01-17 17:31 UTC by András Manţia
Modified: 2004-01-21 08:45 UTC (History)
0 users

See Also:
Latest Commit:
Version Fixed In:


Attachments
patch (1.46 KB, patch)
2004-01-18 06:01 UTC, Jens Dagerbo
Details

Note You need to log in before you can comment on or make changes to this bug.
Description András Manţia 2004-01-17 17:31:14 UTC
KDE CVS from 2004/01/17, File Groups view: 
Problem #1: Turning on/off showing of non-project file is SLOW. 
Problem #2: I have the following groups" 
 Tag descriptions: description.rc 
 User Interface: *.ui;*.rc;*.kdevdlg 
  
My description.rc files are shown under User Interface, not under Tag 
descriptions. This was working before (~1-2 months ago).
Comment 1 Jens Dagerbo 2004-01-17 18:38:53 UTC
I tried using the quanta source.

#1 - Yes, it's slow. 22 sec to turn on "non-project files", 8 sec to turn it off on my box. (with debug area 9017 off) 

Interestingly, on the KDevelop source (which is larger and where I tested) I get 2 and 3 sec respectively. I have less filegroups defined here, but still.. I'll have to look into this.

#2 - This is very non-obvious but.. the matching is actually done against the whole path of the file, not just against the filename. (I personally think this is unintuitive and fairly useless.) You get the group you want by setting the pattern to '*description.rc'.


The whole filegroups widget is nasty, and I'm hoping to create a better one for KDevelop-3.1, if time permits. 

As #2 is technically not a bug, I'm renaming this bug to highlight #1.

Comment 2 Jens Dagerbo 2004-01-18 05:54:56 UTC
Heh. I had another look at what was going on with the quanta setup and source - 3290 files and 38 regexps has a worst case scenario of almost 150000 calls to QRegExp::exactMatch(). This is not going to be fast any contemporary machine.. :)

It is also completely unneccessary. The most common case is going to be suffix matching, and for that a regexp is overkill.

By changing the rules a bit and assuming that a pattern that doesn't contain a wildcard character is meant to be matched against the end of the path and only as a fallback using a regexp, I see the 22 seconds go down to <1 sec. :)

Patch follows.
Comment 3 Jens Dagerbo 2004-01-18 06:01:04 UTC
Created attachment 4222 [details]
patch

Please apply this patch, change the patterns to not have the '*' if they are
meant to be matched as "end-of-string" (that is ".cpp;.cc;.cxx" and
"description.rc", not "*.cpp;*.cc;*.cxx" and "*description.rc" anymore) and
please test. It should be significantly faster.
Comment 4 Amilcar do Carmo Lucas 2004-01-18 20:24:44 UTC
Your patch works and looks good but It still takes 1M40s to load the file groups of the project I'm using :(

And the expressions I'm using do not even include a *
I only use normal stuff (.cpp, .h, README and so on)
:-(
Comment 5 András Manţia 2004-01-19 12:15:56 UTC
Subject: Re:  File Groups performance bad in some cases

I can confirm also that it's way faster, but a little confusing now. I'd 
suggest:

- use the endsWith() matching is the expression has one * and it's at the 
begginning and does not contain ?, [ or ]
- use regular expression matching otherwise
This will be compatible with current rules and we will still gain a lot of 
speedup

Andras

Comment 6 Jens Dagerbo 2004-01-21 08:45:57 UTC
Subject: kdevelop/parts/fileview

CVS commit by dagerbo: 

Improve File Groups plugin performance. Closes bug 72831.

Main part of patch written by Jonas Jacobi. 

CCMAIL: 72831-done@bugs.kde.org


  M +57 -10    filegroupswidget.cpp   1.23


--- kdevelop/parts/fileview/filegroupswidget.cpp  #1.22:1.23
@@ -44,4 +44,32 @@ static const char *translations[] = {
 };
 
+class FileComparator {
+public:
+        virtual ~FileComparator(){
+        };
+        virtual bool matches(const QString& name) const = 0;
+};
+
+class RegExpComparator : public FileComparator {
+public: 
+        RegExpComparator(const QString& pattern) : m_exp(pattern, true, true){
+        }
+        bool matches(const QString& name) const{
+                return m_exp.exactMatch(name);
+        }
+private:
+        const QRegExp m_exp;
+};
+
+class EndingComparator : public FileComparator {
+public:
+        EndingComparator(const QString& pattern) : m_pattern ( pattern){
+        }
+        bool matches(const QString& name) const{
+                return name.endsWith(m_pattern);
+        }
+private:
+        const QString m_pattern;
+};
 
 class FileViewFolderItem : public QListViewItem
@@ -52,5 +80,5 @@ public:
 
 private:
-    QStringList patterns;
+    QPtrList<FileComparator> m_patterns;
 };
 
@@ -60,5 +88,28 @@ FileViewFolderItem::FileViewFolderItem(Q
 {
     setPixmap(0, SmallIcon("folder"));
-    patterns = QStringList::split(';', pattern);
+    m_patterns.setAutoDelete(true);
+    QStringList patternstring = QStringList::split(';', pattern);
+    QStringList::ConstIterator theend = patternstring.end();
+    for (QStringList::ConstIterator ci = patternstring.begin(); ci != theend; ++ci)
+        {
+                QString pattern = *ci;
+                QString tail = pattern.right( pattern.length() - 1 );
+                
+                if ( (tail).contains('*') || pattern.contains('?') || pattern.contains('[') || pattern.contains(']') )
+                {
+                        m_patterns.append( new RegExpComparator( pattern ) );
+                }
+                else
+                {
+                        if ( pattern.startsWith("*") )
+                        {
+                                m_patterns.append( new EndingComparator( tail ) );
+                        }
+                        else
+                        {
+                                m_patterns.append( new EndingComparator( pattern ) );
+                        }
+                }
+    }
 }
 
@@ -69,12 +120,8 @@ bool FileViewFolderItem::matches(const Q
     QString fName = QFileInfo(fileName).filePath();
 
-    QStringList::ConstIterator it;
-    for (it = patterns.begin(); it != patterns.end(); ++it) {
-        // The regexp objects could be created already
-        // in the constructor
-        QRegExp re(*it, true, true);
-        if (re.exactMatch(fName))
+    QPtrList<FileComparator>::ConstIterator theend = m_patterns.end();
+    for (QPtrList<FileComparator>::ConstIterator ci = m_patterns.begin(); ci != theend; ++ci) 
+        if ((*ci)->matches(fName))
             return true;
-    }
 
     return false;