Reverse Order on QStringList slow...?
I must delete file and collection (folder on remote server Webdav) i read file and dir on separate list
from level 0 to infinity down ...
Now to begin to delete file and Dir i must beginn from last level down
and i reverse the list so.....
Code:
{
if (xx.size() == 0) {
return xx;
}
newreversed.clear();
bool walking = true;
int o = xx.size();
for (;walking;) {
o--; /* size 1 goto 0 ; size 2 start on 1 end on 0 */
newreversed.append(xx.at(o));
if (o == 0) {
walking = false;
}
}
return newreversed;
}
I suppose and i see now is very slow the action why?
is ther a other method to reverse a list?...
If You have a remote webdav dir ..... can you test the application?
curl -O http://ppk.ciz.ch/qt_c++/webdavdir.tar.gz
tar -zxvf w* && cd w*
qmake a.pro && make
./webdav
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
patrik08
is ther a other method to reverse a list?...
Code:
#include <algorithm>
std::reverse(xx.begin(), xx.end());
But you don't have to reverse the list to iterate it in reverse order... QList has an index based way of accessing items, so you can just make a for loop:
Code:
for(int i=xx.size()-1; i>=0;i--){
doSomething(xx.at(i));
}
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
patrik08
I must delete file and collection (folder on remote server Webdav) i read file and dir on separate list
from level 0 to infinity down ...
Now to begin to delete file and Dir i must beginn from last level down
and i reverse the list so.....
Are you sure that reversing the list is your problem? (Beside that you do not even need it as wysota mentioned ;-)
I just wrote a (completly unscientific but good enough to get an idea) benchmark for it...and it does not seem to take that much time.
Here is my test prog (with an other implementation of reverse that does only take about half of the time):
Code:
#include <QtCore>
{
if (xx.size() == 0) {
return xx;
}
newreversed.clear();
bool walking = true;
int o = xx.size();
for (;walking;) {
o--; /* size 1 goto 0 ; size 2 start on 1 end on 0 */
newreversed.append(xx.at(o));
if (o == 0) {
walking = false;
}
}
return newreversed;
}
{
if (list.isEmpty()) {
}
const int listSize = list.size();
const int maxSwap = list.size() / 2;
for (int i = 0; i < maxSwap; ++i) {
qSwap(reversedList[i], reversedList[listSize - 1 -i]);
}
return reversedList;
}
int main(int argc, char* argv[])
{
Q_UNUSED(argc);
Q_UNUSED(argv);
for (int i = 1; i < 100; ++i) {
}
const int iterations = 1000000;
{
for (int j = 1; j < iterations; ++j) {
if (testList != oldReverseList(reversedList)) {
qFatal("reverseList is broken");
}
}
qDebug() << iterations * 2 << "iterations of oldReverseList in" << start.secsTo(stop) << "seconds ";
}
{
for (int j = 1; j < iterations; ++j) {
if (testList != newReverseList(reversedList)) {
qFatal("reverseList is broken");
}
}
qDebug() << iterations * 2 << "iterations of newReverseList in" << start.secsTo(stop) "seconds";
}
return 0;
}
The results that I got were:
Quote:
2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds
Re: Reverse Order on QStringList slow...?
The results are obvious and the benchmark is not needed :) If you do half the amount of iterations, you'll get half amount of effort to complete the task ;) I'm pretty certain std::reverse uses the same algorithm your newReverse does (as there is no "temporary" or "second" list so it has to store objects in the list itself and the easiest way to do that is to just swap the items).
Anyway I think the problem is not in the list (like already mentioned) but on the deleting algorithm... Why do you need those two lists (dirs/files)? Can't you do a recursive delete of the root directory?
Pseudocode follows:
Code:
bool deleteDir
(const QString &path
){ bool good = true;
if(isFile(entry))
good = deleteFile(path+entry);
else if(isDir(entry))
good = deleteDir(path+entry); // recursive call here
if(!good)
return false; // bail out on error
}
return deleteSelf(path);
}
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
wysota
The results are obvious and the benchmark is not needed :) If you do half the amount of iterations, you'll get half amount of effort to complete the task ;) I'm pretty certain std::reverse uses the same algorithm your newReverse does (as there is no "temporary" or "second" list so it has to store objects in the list itself and the easiest way to do that is to just swap the items).
Actually they are not 100% obvious, depending of you viewpoint. I am thinking about memory allocation problems.
When you have a QList and fill them one by one, you might get problems with reallocation, as the QList needs more memory.
I first thought about experimenting with that, using reserve(as in QVector::reserve()) ... until I noticed that there is not such a thing in QList ;-)
Thus, copy and detach :-)
qSwap has another (very slight) advantage over using the std algorithms (at least when using with implicitly shared Qt types, and types sufficiently declared using Q_DECLARE_TYPEINFO) as it does some bad magic if the type is only the size of a pointer. This saves some atomic operations compared to doing it via three way operator=().
TIP: Qt has a nice collection of algorithms for containers :-)
But I guess this transgresses into the realm of the very off topic ;-)
[And: these kind of optimizations should only be taken out of the safe when everything else is failing...which it they do not at this point ;-) ]
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
wysota
I'm pretty certain std::reverse uses the same algorithm your newReverse does
Actually I just added a stdReverseList to the mix
Code:
{
std::reverse(reversedList.begin(), reversedList.end());
return reversedList;
}
Result:
Quote:
2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds
2000000 iterations of stdReverseList in 14 seconds
My totaly unscientific guess to explain the result, would be that access via the iterators (as needed by std::reverse) is slower than access via operator[]...
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
camel
When you have a QList and fill them one by one, you might get problems with reallocation, as the QList needs more memory.
Yes, but the list doesn't allocate one by one, it does a preallocation.
Quote:
I first thought about experimenting with that, using reserve(as in
QVector::reserve()) ... until I noticed that there is not such a thing in QList ;-)
It wouldn't have much sense. QVector expands in one direction (items are "appended" to the end), whereas QList can grow in two directions (items can be "appended" or "prepended"). Reserve would not make much sense then, you'd need two methods instead ("reserveAtEnd" and "reserveAtFront"). But you can subsitute QStringList with QVector<String> without any performance loss as in this situation items are only added to the end, not anywhere inbetween or in front.
Quote:
qSwap has another (very slight) advantage over using the std algorithms (at least when using with implicitly shared Qt types) as it does some bad magic if the type is only the size of a pointer. This saves some atomic operations compared to doing it via three way operator=().
Yes, it can actually exchange the values, but the value needs to be memmovable.
About the speed of std::reverse - the use of iterators should slow QList down that much. I'm convinced that the iterator in QList is not much more than item index, so access to an element should always be O(1). Operator= for QList has the same features qSwap has and additionally QString is pretty fast on its own, so that also should have such a big influence. My guess is that std::reverse is simply slow :)
Actually I just checked my implementation of std::reverse:
Code:
{
while (true)
if (__first == __last || __first == --__last)
return;
else
{
std::iter_swap(__first, __last);
++__first;
}
}
It uses the exact same algorithm your fast implementation uses. So the slowdown has to be either in QList itself or in std::iter_swap.
Re: Reverse Order on QStringList slow...?
I made a test using a QVector based implementation of the oldReverseList function that preallocates all the needed memory in the constructor.
Code:
2000000 iterations of oldReverseList in 18 seconds
2000000 iterations of oldReverseList2 in 15 seconds
It's slightly faster, but I wouldn't call it a big difference.
The implementation:
Code:
static inline QVector<QString> oldReverseList2
(const QStringList &xx
) {
if (xx.size() == 0) {
return QVector<QString>();
}
QVector<QString> newreversed(xx.size());
int s = xx.size();
int li = 0;
for(int i=s-1; i>=0;i--) {
newreversed[li++] =xx.at(i);
}
return newreversed;
}
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
wysota
So the slowdown has to be either in QList itself or in std::iter_swap.
We have a winner ;-)
I added the (not very beautifull) reimplementation of std::reverse using qSwap:
Code:
{
{
while (true)
if (__first == __last || __first == --__last)
return reversedList;
else
{
qSwap(*__first, *__last);
++__first;
}
}
}
The result:
Quote:
2000000 iterations of oldReverseList in 14 seconds
2000000 iterations of newReverseList in 8 seconds
2000000 iterations of stdReverseList in 14 seconds
2000000 iterations of std2ReverseList in 6 seconds
This means this is the (in the moment) speediest implementation, and the problem is in std::iter_swap
;-)
Re: Reverse Order on QStringList slow...?
the fasted solution is to read list reverse .....
and QStringList::appends(QStringList other list) not exist.....
Code:
void Gui_Remove::WakeUpsFile()
{
CodaonDelete.clear(); /* container file and dir */
passaggiwake++;
//////////qDebug() << "####LISTTOBE REMOVE ->" << passaggiwake << "-" << startpath;
if ( passaggiwake >= 2) {
return; /* break if like read a 2° time and delete not exist file */
}
QStringList RFile
= ReverseList
(Del_File
);
/* reverse list from file delete file on top */
for (int i = 0; i < RFile.size(); ++i) { /* to save time only read reverse the list */
//////////qDebug() << "###file del -> " << RFile.at(i);
CodaonDelete.append(RFile.at(i));
}
QStringList RDir
= ReverseList
(Del_Dir
);
/* reverse list from dir delete dir on last action */
for (int i = 0; i < RDir.size(); ++i) {
//////////qDebug() << "###dir del -> " << RDir.at(i);
CodaonDelete.append(RDir.at(i));
}
Del_File.clear();
Del_Dir.clear();
Del_Work_Grep.clear();
if (CodaonDelete.size() > 0) {
CodaRemove(0);
}
}
void Gui_Remove::CodaRemove( int now ) /* loop all dir and file list send to class delete */
{
if (aborter) { /* button abort delete */
return;
}
int bigmap = CodaonDelete.size();
if (bigmap == 0) {
CodaonDelete.clear(); /* sure */
LastRemove(); /* remove the last on top path */
return;
}
if (now >= bigmap) {
CodaonDelete.clear();
LastRemove(); /* remove the last on top path */
return;
}
for (int i = 0; i < CodaonDelete.size(); ++i) {
if (now == i) {
QString anextpath
= RealRemotePath
(CodaonDelete.
at(i
));
if (anextpath.size() > 0) {
label->setText(tr("Pending operation on: %1").arg(RealRemotePath(startpath)));
label_2->setText(tr("Remove wait: %1").arg(anextpath));
DavDelete *lismix = new DavDelete(dbdav,anextpath); /* file or dir */
lismix->SetPosition(now);
connect(lismix,
SIGNAL(WarningMsg
(QString)),
this,
SLOT(ShowMessageWarning
(QString)));
/* abort the loop */ connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int))); /* continue delete from path down to up */
} else {
CodaRemove(now + 1);
}
return;
}
}
}
Re: Reverse Order on QStringList slow...?
Just to post my latest findings (of how you can speed up standard algorithms when you work with Qt types)
I simply added the following code:
Code:
static inline void swap(QString& a, QString& b)
{
qSwap(a,b);
}
That changed the result to:
Quote:
2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds
2000000 iterations of stdReverseList in 7 seconds
2000000 iterations of std2ReverseList in 6 seconds
That means you get very easily a great(*) speedup because the STL can now use the optimizations used in qSwap. (Still not as fast as the overall winner here, but the absolute winner in the work/result ratio category :-)
(*): "great" of course only if you do 2000000 million iterations of a reverse list algorithm...which you probably do not do ;-)
but its probably a thing to keep in mind if you find the std algorithms taking too long for your taste :-)
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
patrik08
the fasted solution is to read list reverse .....
Well yeah...but it's not as much fun ;-)
Quote:
Originally Posted by
patrik08
and QStringList::appends(QStringList other list) not exist.....
Use operator+=
Looking at your code...have you thought about using a QStack?
you just QStack::push() whatever you find you need to delete onto it, and when you want to do it you simple QStack::pop() the contents of the stack until it is empty....
Re: Reverse Order on QStringList slow...?
Doing a delete with a stack (pseudo-code)
Code:
bool recursiveDeleteDir
(const QString &path
){ QStack<QString> currentPathStack;
QStack<QString> deletablePathStack;
currentPathStack.push(path);
while (!currentPathStack.isEmpty()) {
QString currentPath
= currentPathStack.
pop();
if (!isDeletableDir(currentPath))
return false;
if(isFile(entry) && isDeletableFile(entry)) {
deletableFileList << entry;
} else if (isDir(entry)) {
currentPathStack.push(entry);
} else {
return false;
}
}
deletablePathStack.push(currentPath);
}
foreach
(QString file, deletableFile
) { if (!deleteFile(file)) {
return false; //ERROR: if you get these, your isDeletableFile got a hickup :-/
}
}
while (!deletablePathStack.isEmpty()) {
if (!deleteDir(deletablePathStack.pop())) {
return false; //ERROR: if you get these, your isDeletableDir got a hickup :-/
}
}
return true;
}
Re: Reverse Order on QStringList slow...?
Hmmm... to delete on a local pc a dir recursive .... i not write 200 feet code...
Code:
/* remove dir recursive */
{
if (dir.exists())
{
const QFileInfoList list = dir.entryInfoList();
for (int l = 0; l < list.size(); l++)
{
fi = list.at(l);
if (fi.isDir() && fi.fileName() != "." && fi.fileName() != "..")
DownDir_RM(fi.absoluteFilePath());
else if (fi.isFile())
{
bool ret = qt_unlink(fi.absoluteFilePath());
if (!ret) {
//////Api_Log("Can't remove: " + fi.absoluteFilePath() + " (write-protect?)");
}
}
}
dir.rmdir(d);
}
}
My problem is to delete on remote server file and path.....
to delete dir i and file i have only a class ....
new QHttp();
QHttpRequestHeader header("DELETE", pathorfile ,1,1); /* header */
http://www.webdav.org/specs/rfc2518....ection.8.6.2.1
Code:
DavDelete *lismix = new DavDelete(dbdav,anextpath);
lismix->SetPosition(now);
connect(lismix,
SIGNAL(WarningMsg
(QString)),
this,
SLOT(ShowMessageWarning
(QString)));
connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int)));
and i have only QStringList from file and Dir or a domdocument like this...
http://ppk.ciz.ch/qt_c++/davinfo.xml
to display tree folder like mc gui....
http://ppk.ciz.ch/qt_c++/davexplorer.png
Re: Reverse Order on QStringList slow...?
I don't see a difference between local and remote delete. The mechanism is the same, you only call a different method to do the actual delete.
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
patrik08
If the first two lines are the contents of your DavDelete, may I propose to you to change the class to take a list of files to delete?
The problem with your approach is that for every delete a new connection to the webdav server is created, while if you would create multiple requests on a single QHttp the same connection might be used, which is generally faster (even more so if the server and QHttp can do pipelining..but I do not know that).
(Disregard if you are actually doing this ;-)
The recursiveDeleteDir approach I posted would work very well for that, since you have, at the end, a list of all paths and files to delete (even in the right order so that you can delete them in a row without error) which you would just have to send to the WebDav server.
[For this to work efficiently, you must have the isFile, isDir children etc. function only using a local cache of course ;-)]
Re: Reverse Order on QStringList slow...?
Quote:
Originally Posted by
wysota
I don't see a difference between local and remote delete. The mechanism is the same, you only call a different method to do the actual delete.
The difference is local remove is a function running on self.... and no signal!!!
function remove( path ) { /* start on top and work to down */
make ....
next level remove(here);
}
on Remote each action must start a signal go delete and emitter go back to next file or dir ..... /* from down dir comming up at end remove the top folder... */
I suppose a multi QThread can handle this .... only one signal to QHttp -> 50 file and dir can delete a dir recursive musch faster.... but a clean example from QThread in to wiki as a multiple action i dont found .... only print A or B sample... to console .... same as the QT4 book from Mister Blanchette and QThread stay a mistery long long time....
Re: Reverse Order on QStringList slow...?
Code:
static inline int addDeleteRequest
(QHttp *http,
const QString
& name
) {
}
bool recursiveDeleteDir
(const QString &path
){ QStack<QString> currentPathStack;
QStack<QString> deletablePathStack;
currentPathStack.push(path);
while (!currentPathStack.isEmpty()) {
QString currentPath
= currentPathStack.
pop();
if (!isDeletableDir(currentPath))
return false;
if(isFile(entry) && isDeletableFile(entry)) {
deletableFileList << entry;
} else if (isDir(entry)) {
currentPathStack.push(entry);
} else {
return false;
}
}
deletablePathStack.push(currentPath);
}
// CONNECT deleterHttp HERE
foreach
(QString file, deletableFile
) { addDeleteRequest(deleterHttp, file);
}
while (!deletablePathStack.isEmpty()) {
addDeleteRequest(deleterHttp, deletablePathStack.pop());
}
QObject::connect(deleterHttp,
SIGNAL(done
(bool), deleterHttp,
SLOT(deleteLater
()));
return true;
}
Re: Reverse Order on QStringList slow...?
I Like Test now "QStack<QString> currentFile;" to download/upload ( rsync like ) a remote dir recursive .... from a remote webdav server .... on Webdav exist a
<lp1:getetag>"bcd40-8ae-cf1a0340"</lp1:getetag> a md5 like param ....
i must only discover a way to save this getetag (filename;getetag;lastmodtime) local in to dir from file .... and remove local the getetag string if a file is updated local to become upload true...
if the remote getetag & the local getetag is same file is sincro true (same version) ... & if a local getetag exist and online getetag is different must download the new version... && update this getetag local....
http://www.webdav.org/specs/rfc2518....OPERTY_getetag
RSync-clone via WebDav - Possible Approaches
I am truly sorry, but I have sadly no idea what the problem is you are trying to express.
My Guess is you are:
- Trying to create rsync like functionality on top of webdav
- Trying to use the entity tags as a way to see if a file has changed?
Simplest way:
Ignore the entity tag, and only use the last modified date (compare the one from the webdav with the one locally, taking into account the different times of the computers).
Harder way:
Store the entity tag of a file together with the lastmodified time of the file(when you knew that the file was identical to the one on the server) and a md5/sha1 sum of the file.
When you want to check for equality server/local
- If the tag you stored is equal to the one the server tells you, check if the file still has the same modified date and if: great they are equal.
- If the tags are equal and the modified date of the file and the stored one are different, compare the stored md5/sha1 sum to the real one of the file. If they are equal...well we do not care if it was "modified" but not changed. => files are equal
- If tags are equal and the modified since and the md5/sha1 sum is different => local file has changed
- If the tag from the server differs from the stored tag, you would update it. But you might still want to check if the file has changed locally...and if, you have a very nice conflict...
Why do you have to do it like this?
You have no guarantee that anyone who modifies your files will delete the entity tag you stored for it....
How to store?
Probably easiest way is a very simple sqlite database using the QSql classes.
Or you could create an xml file somewhere with that data...or use qsettings or.....
EDIT: This really gets off-topic if you look at the post-title...;-)
