C / C++ / MFC

500% perf improvement in Release build?

22-May-01 4:25

Hello,

I just converted an article at the "other" site (http://www.codeguru.com/listview/VirtualListControl.html) from CArray to std:vector. The performance increased 5 times! The only section that I didn't like was the column sorting method. It uses the qsort() function to sort the columns. It seems there would be a more elegant (STL) method of doing this. There is a class defined for a row of data similar to this (shortened for clarity):

class CRowData {
CString col1;
int col2;
}

The qsort function calls the appropriate comparison function to sort on the desired member. It seems like there should be a way to do this using the STL. I would like to expand this example to include sorting on more than two columns as well.

Any ideas?

Thanks,
Derek

Doble Engineering

Tomasz Sowinski22-May-01 4:39

Re: 500% perf improvement in Release build?

22-May-01 4:39

Are you also getting 500% performance improvement in Release build?

Tomasz Sowinski -- http://www.shooltz.com.pl

Derek Price22-May-01 4:57

Re: 500% perf improvement in Release build?

22-May-01 4:57

Actually it's not as high as I thought. I was comparing debug build to debug build. Using the metrics (GetTickCount) the original author already had in the code (approximate tick values):

CArray:
Debug: 2000
Release: 250

STL:
Debug: 600
Release: 90

List Control InsertItem():
Debug: 15000
Release: 12000

STL Improvement:
Debug: ~ 3.3x
Release: ~ 3.3x

These are after a few runs, but there was definitely an improvement. Either was an improvement over the InsertItem method! I know all of these results are completely subjective (compiler settings, computer speed, etc.), but try it yourself to see the difference!

Also, any ideas on converting the sorting to STL?

Thanks,
Derek

DP

Tomasz Sowinski22-May-01 6:26

22-May-01 6:26

The speed increase you're experiencing is caused by smaller number of memory reallocations when you add items to your array/vector. CArray grows by constant number of elements, while std::vector (version shipped with VC++) doubles its buffer size when it needs to grow.

Access time to array/vector elements should be identical in Release build - it's *very* simple container; compiler should generate almost identical code. In Debug build, the story is different: STL implementation that ships with VC++ DOES NOT check indices in vector::operator[]. If you're a former CArray user, this may come as total suprise - you can v.resize(10) your vector and use v[100] without assert. In other words, in Debug CArray will be slower, but safer.

The freely available STLPort (www.stlport.org) performs index overflow checking in debug build - I strongly recommend this version of STL.

Tomasz Sowinski -- http://www.shooltz.com.pl

C^hris L^osinger22-May-01 6:03

C^hris L^osinger

22-May-01 6:03

take a look at std::sort

-c

------------------------------
Smaller Animals Software, Inc.
http://www.smalleranimals.com

Derek Price22-May-01 6:19

22-May-01 6:19

I thought about this, but I'm not sure how to approach it. If I have a class:

class CRowData {
CString col1;
int col2;
}

and I defined a vector as:

std::vector<crowdata> vecRowData;

and I want to use std::sort, then I have to override the operator< and operator==. This means I can only sort on one variable in the operator< method. How can I specify which variable to sort on?

DP

Tomasz Sowinski22-May-01 6:36

22-May-01 6:36

Use std::sort that takes three arguments. The last one is a predicate - you can pass one predicate when you need to sort by col1, another for col2.

Since it seems that performance is important to you, note that while qsort just shuffles bits around during sorting, std::sort will perform assignments. Depending on members of your struct, it may have impact on perf. Post some results when you're done with this Smile | :)

Tomasz Sowinski -- http://www.shooltz.com.pl

C^hris L^osinger22-May-01 6:51

C^hris L^osinger

22-May-01 6:51

there are many flavors of std::sort. some of them take what's called a 'predicate'. this is essentially a custom comparison function. so, you can sort on anything you like.

bool predicateFunction(const CMyStruct& a, const CMyStruct& b)
{
  return (a is somehow less than b);
}

vector <CMyStruct> vec;
...
std::sort(vec.begin(), vec.end(), predicateFunction);

so, you just use different predicate functions when you want to sort in different ways (differnet members, direction, etc.)

-c

------------------------------
Smaller Animals Software, Inc.
http://www.smalleranimals.com

Derek Price22-May-01 7:49

22-May-01 7:49

Thank you for the code snippet! It was just what I needed! I created two sort functions:

bool sortCol1(const CLabelItem& a, const CLabelItem& b)
{
return (a.m_strText < b.m_strText); // CString
}

bool sortCol2(const CLabelItem& a, const CLabelItem& b)
{
return (a.m_Addr < b.m_Addr); // DWORD
}

and did the sort comparision only on the STL modified code. Here are the results (in ticks) for 50000 rows:

Debug Release
qsort:
CString 55000 22000
DWORD 220 50

STL sort:
CString 1221 420
DWORD 750 220

Summary ( IMHO Smile | :)

)
Use STL for code simplicity and maintenance and use STL sort unless the extra 150 ticks for DWORDs are important!

My thanks to all for all the help!

Derek

Tomasz Sowinski22-May-01 10:58

22-May-01 10:58

So the qsort is *much* slower for CString sorting? It's rather counter-intuitive, but still possible. Could you post your function that qsort calls back?

Tomasz Sowinski -- http://www.shooltz.com.pl

Derek Price23-May-01 7:05

23-May-01 7:05

Well,... I "screwed up" again Smile | :)

I guess I was comparing apples and oranges. The qsort method used the strcmp (C-runtime) function to compare strings. I used CString's operator> method to compare. Both give the same answer, but the CString was much faster. I didn't bother replacing the STL sort code with the strcmp code, because I'm sure it would be slower than qsort's.

Sorry for the misleading results!

Derek

STL & List Control

Derek Price22-May-01 4:25

clicking on a listbox created in runtime over an edit control in a formview

22-May-01 4:25

Workspace setup

Roger22-May-01 4:07

Roger

22-May-01 4:07

Where is the flag that I can set in MS Visual C++ that will allow me to have an instance of MS Visual C++ open, then double click a .dsw in Windows Explorer and have that workspace open in another instance of MS Visual C++? I know I have something set somewhere that allows this, I just cannot remember. Any help?

Roger Printy
Software Engineer
TeraNex
Orlando, FL

VSS and C++ automation

22-May-01 2:42

Is there a way using the C++ automation to find out the location of the project/file in the SourceSafe?
The only solution that I see for now is to find out the path of the project and than to parse the .dsp or .dsw file to find out the path of the project in the SourceSafe.
I would like to do this without parsing the .dsp or .dsw file...

Thanks.

Rasstislav

22-May-01 2:23

when trying to click on a listbox created in runtime over an edit control in a formview, the existing edit control under the listbox control gets a focus. so i can't select an item in a listbox. somebody help me... Frown | :(

by peng-you.

Re: clicking on a listbox created in runtime over an edit control in a formview

l a u r e n22-May-01 23:40

l a u r e n

22-May-01 23:40

hmmmm
try either setting the z-order of the listbox to be in front of the edit control ... maybe destry the edit control ... disable it ... or use a combobox that allows the user to type stuff into the list control portfion and add some custom behaviour to stop the item being added to the list

---
"every year we invent better idiot proof systems and every year they invent better idiots"

Directory Selection using File Dialog

22-May-01 2:13

How can I make my CFileDialog to accept directories and return the full path name of the directory. Something like what I get when I select File / New option in the MSDEV IDE and click on the "..." button next to Location Edit box ??

Sudha Shriram

Re: Directory Selection using File Dialog

Tomasz Sowinski22-May-01 2:18