C / C++ / MFC

22-Jun-09 8:42

I am attempting to create a template that has a constructor that takes an array of items of type T, declared as follows:

template <typename T>
class foo {
public:
    foo(T* items) {
        // Initialize foo
    }
};

Unfortunately, this code will not compile if T is a reference type, because you cannot have pointers to references. Therefore, I would like to create a template specialization that only declares this method if the template parameter T is NOT a reference variable. If it is a reference variable, I want the same method signature but I would like it to be an array of non-reference types to the class. As an example, if I knew that the template parameter base type was 'int', I could create the following specializations:

template <int>
class foo {
public:
    foo(int* items);
};

template <int&>
class foo {
public:
    foo(int* items);
};

template <int*>
class foo {
public:
    foo(int** items);
};

template <(int& )*>
class foo {
public:
    foo(int** items);
};

However, I don't know what base type the template parameter is, so I would like to do the above specialization for any base type (for example, I used int, but I could have used string, unsigned, char, or any other class). Is there any way to do this? Thanks,

Sounds like somebody's got a case of the Mondays

-Jeff

Stuart Dootson22-Jun-09 9:31

22-Jun-09 9:31

Does this meet your needs? It compiles (and runs OK) with gcc 4.0.1, should compile with Visual C++ 7.1 and above, I believe. The Boost type traits[^] do the template specialisations for you, in the derivation of the constructor parameter type.

#include <boost/type_traits.hpp>
#include <iostream>

template <typename T>
class foo {
public:
    foo(typename boost::add_pointer<typename boost::remove_reference<T>::type >::type items)
    {
      // Do Stuff
    }
};

int main()
{
   int aa;
   foo<int> a(&aa);
   foo<int&> b(&aa);
}

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Skippums23-Jun-09 3:22

23-Jun-09 3:22

This is great advice... I think I am going to hold off on it for now and just delete those constructors so I don't have to install a third-party package, but I will keep this in mind for future work as this appears to be very useful information.

Sounds like somebody's got a case of the Mondays

-Jeff

Stuart Dootson23-Jun-09 3:36

23-Jun-09 3:36

That part of Boost wouldn't need much installation - the type-traits are a header-only library, so don't need anything to be built.

Alternatively, with a decent standard compliant compiler (like VC++ 7.1 and later), those type traits are easy enough to write, especially for the case you have:

template<class T>
struct add_pointer
{
   typedef T* type;
};

template<class T>
struct add_pointer<T&>
{
   typedef T* type;
};

I've just built and run that with VS2008 (admittedly only with simple types like int) and it seems fine.

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Nemanja Trifunovic22-Jun-09 9:34

Nemanja Trifunovic

22-Jun-09 9:34

Have you looked at partial template specialization? You could make a partial specialization for reference types and then a general template for the rest of them.

Programming Blog

utf8-cpp

Skippums22-Jun-09 9:52

22-Jun-09 9:52

Do you know the syntax to do such a thing? That is exactly what I am attempting to do, but have no idea as to the syntax. Thanks,

Sounds like somebody's got a case of the Mondays

-Jeff

Performance problem with my FindOneOf function [modified]

Nemanja Trifunovic22-Jun-09 10:04

Nemanja Trifunovic

22-Jun-09 10:04

From the top of my head (untested) something like:

template <typename T>
class foo<T&>
{
...
};

Programming Blog

utf8-cpp

Ivan Ivanov 8322-Jun-09 4:09

22-Jun-09 4:09

Hi All

I'm developing my own CString class. With the idea to make it "much" faster than the standard CString, easily upgradeable, and to include into it some non-standard parsing functions I often use in my work, those will be much better to be part of the CFString object itself, instead of being separate functions.
And in deed I have some noticeable achievements for the basic functions my CFString uses:

My copy() is 35% faster then strcpy()!

My lengh() is 30% faster than strlen().
BUT note that the optimizer often pre-calculates strlen() calls and replaces them with respective numbers!
For example int i = strlen("abc") will eventually generate mov EAX, 3 instaed of generating the asm code of strlen() itself, that happens for hardcoded strings! so in the cases when strlen() isn't replaced by a number, my function is 30% faster

My compare() is 20% faster than strcmp().

I used the inline assembly option of the Visual C++ compiler, the "__asm" command to achieve this.

I also developed an equalizing mechanism, so when I write str1 = str2 the "operator =" actually doesn't copy the data from str2 to str1
the copy occurs ONLY in specific cases when it's needed.
And that mechanism provides about 35 - 40% faster equalizing betweend CFString objects in comparison to the CString equalizing!

So far so good! But in the case with FindOneOf the standard CString beated me badly! CString::FindOneOf is almost twise faster than my CFString::FindOneOf, and my FindOneOf IS written in assembly too. I did everithing I could to tweak it up, but I only reduced the time from 33000ms to 28000ms and CString::FindOneOf does the job for 18000ms, and my function suppose to be faster, now I'll be happy just to equal the score of CString::FindOneOf!
This is the test code I use:

CString/CFString str1("abcdefghijklmnoprs0987654321");

int start = GetTickCount();
for(int pos = 0; pos; 100000000; pos++)
{
    index = 0;
    index = str1.FindOneOf("1234567890");
}
int time = GetTickCount() - start;

CString strTime;
strTime.Format("%d, %d", time, index);
m_editResult.SetWindowText(strTime); //this is the CEdit object I use for output

I looked at the disassembly of the CString::FindOneOf but couldn't find a single loop, I didn't understan anything! there are a lot of stack operations (PUSH POP) a lot of CALLs and they suppose to be slow, I don't have any idea how can this function beat mine!!!
This is the algorithm I use written in C, although it's written in assembly and I believe optimised in the actual function:

    const char* pstrTBuffer = m_pstrBuffer; //the actual string
const char* pstrTSeek   = pstrSeek; //the charset
do
{
    while(*pstrTSeek)
    {
        if(*pstrTBuffer == *pstrTSeek++)
        {
            return pstrTBuffer - m_pstrBuffer;
        }
    }
    pstrTSeek = pstrSeek;
}
while(*++pstrTBuffer);
return -1;

In case the code isn't clear enough:
The idea is as simple as possible, compare each character in the main string m_pstrBuffer with each character in the charset pstrSeek
if there is a match return its index if not return -1

I assumed that the problem isn't in my coding technique, it must be generally in the algorithm I use!!!
Does somebody know a better algorithm to implement FindOneOf??? Smile | :)

I will appreciate any help - thank you!!! Smile | :)

Sorry for the prolonged question, but I wanted to be as clear as I can in my description.

modified on Monday, June 22, 2009 10:20 AM

Stuart Dootson22-Jun-09 8:46

22-Jun-09 8:46

Member 4399131 wrote:
I assumed that the problem isn't in my coding technique, it must be generally in the algorithm I use!!!

Yep.

Member 4399131 wrote:
Does somebody know a better algorithm to implement FindOneOf???

Looking at their code (strpbrk - actually implemented using strspn), Microsoft do Smile | :)

They build a table (it's only 256 bits == 32 bytes) from the set of characters you're looking for and do a table lookup for each character of the string you're searching in. That means that their algorithm is O(n) (n=search string length) rather than O(n*m) (n=search string length, m=number of chars you're looking for).

Oh, and they implement that in assembly language (different implementations for x86 and x64). If I were you, I'd do myself a favour and use the MS C run-time function in this case...

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Ivan Ivanov 8322-Jun-09 22:30

22-Jun-09 22:30

Check this out Smile | :)

It seems the the test code wasn't appropriate

CString str2[] = { "1234567890", "qwtyupzxghiocervbasdjklfnm", "qwo123ertyui45", "qwzxy1uldfghjk2bnm3ertcviopas" };

int index = 0;
CFString str1("abcdefghijklmnoprstuzxwvqyqwertyuio0987654321");

int i = 0;
int start = GetTickCount();
for(int pos = 0; pos < 100000000; pos++)
{
    index = 0;
    index = str1.FindOneOf(str2[pos % 4]);
}
int time = GetTickCount() - start;

CString strTime;
strTime.Format("%d, %d", time, index);
m_editResult.SetWindowText(strTime);

In this eaxmple which includes a number of different charsets my function finishes for 19000ms and CString::FinOneOf for 25450ms which is 6468ms slower, in other words my function is 25% faster. Do you think that this test code is more accurate?

And about the MS Lookup table I look at it too and I wonder if that's quite legal, I mean that according to my assembly book the instruction BTS sets a bit in the target pointed by its position BUT MAX POSITION IS 31!!! in this case they set bits in a larger memory block by setting positions up to 255 - I wonder how this works, it does obviously?! Maybe my assembly book is obsolete.

Stuart Dootson22-Jun-09 22:48

22-Jun-09 22:48

Member 4399131 wrote:
It seems the the test code wasn't appropriate

Member 4399131 wrote:
Do you think that this test code is more accurate?

The only really accurate test set would exercise all possible inputs...which is obviously infeasible Smile | :)

What's more important is to understand why your code is quicker with some test sets and not with others and to determine what the optimal approach actually is (for example, if you can work out roughly where your code becomes more efficient than Microsoft's, you could switch between the two implementations dynamically).

Member 4399131 wrote:
And about the MS Lookup table I look at it too and I wonder if that's quite legal, I mean that according to my assembly book the instruction BTS sets a bit in the target pointed by its position BUT MAX POSITION IS 31!!! in this case they set bits in a larger memory block by setting positions up to 255 - I wonder how this works, it does obviously?! Maybe my assembly book is obsolete

My x86 reference (pukka Intel reference manual) says that if you use an immediate operand, you're limited to 0-31. If you use a register operand, the limits disappear (well, they're -2^31 to 2^31-1, which is near as damn it unlimited)

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Ivan Ivanov 8323-Jun-09 0:32

23-Jun-09 0:32

Stuart Dootson wrote:
switch between the two implementations dynamically

that's a GOOD idea! Smile | :)

Stuart Dootson wrote:
if you use an immediate operand, you're limited to 0-31. If you use a register operand, the limits disappear

I seeeee! this detail wasn't written in my source - that's a reason to find some more complete one. Wink | ;)

Actually when I look at strspn I see some good tweaks could be done, so I'll try them...
The research continues... Thumbs Up | :thumbsup:

Stuart Dootson23-Jun-09 0:41

23-Jun-09 0:41

Member 4399131 wrote:
I seeeee! this detail wasn't written in my source - that's a reason to find some more complete one.

I got mine from Intel[^] - downloadable PDFs these days. When I got them (close to 10 years ago!) you could order free paper manuals and they'd dispatch them to you, again free. I guess the cost of that was an easy target when reducing costs, as paper copies of the manuals now cost money (and lots of it!).

I see (by downloading the PDFs) that BTS actually gives you offsets of up to +/- 2^63 bits on the IA-64 (== x64) platform. Should be enough, even for Unicode lookup tables Smile | :)

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Ivan Ivanov 8323-Jun-09 4:17

23-Jun-09 4:17

Wow! thank you man! Smile | :)

for some time I was wondering where I can get such a detailed description of the architecture and each instruction(I didn't even know how to search for it), and not thanks to you I finaly have it!!! - MY REGARDS Smile | :)

Bay the way I didn't bother myself ordering it - I've downloaded it directly in PDFs Wink | ;)

Ivan Ivanov 8324-Jun-09 1:11

24-Jun-09 1:11

I did it!

I used the lookup table algorithm implemented in my own coding technique (which is nothing special just few tweaks). And now I have FindOneOf that is 15 - 25% faster than CString::FindOneOf. I did many tests and it doesen't drop bellow 15% Wink | ;)

I couldn't make it without your help! THANK YOU!! Smile | :)

It would be even faster but BT, BTS as well as SHR, SHL, ROR, ROL (and others) instructions are generally slower than MOV, ADD and so on ... instructions!
I noticed that in my not very long assembly practice. I think that is because they are all bitwise operations.

Skippums22-Jun-09 9:02

22-Jun-09 9:02

Without knowing the logic behind the standard implementation, it is impossible to know why your algorithm is being beat. Perhaps the standard string stores data about specific searches so that, in your loop, it loads known results instead of recalculating them (ie, you are searching the same string for the same charset, so why not cache the result?). Perhaps it realized that your set of input characters is consecutive, and instead of iterating through them it tests each character against a range. Perhaps the standard implementation starts from the end of the string and searches forward. Perhaps the compiler realized that the standard call to FindOneOf in your loop could be optimized away since you are not using any values of that method call except the final one, but your inline-assembly could not be optimized away. The moral is, without doing more testing I have no idea why your algorithm is slower (or your test method is inappropriate). I would only recommend additional test cases, or to make one or more of the modifications that I said were possibilities of what the standard code does. You could also try reordering the loops, but I doubt you are going to see significant timing differences resulting from such a change.

[BEGIN EDIT]
The lookup table idea is a great one for ASCII strings... I was only thinking in terms of unicode.
[END EDIT]

Sounds like somebody's got a case of the Mondays

-Jeff

Stuart Dootson22-Jun-09 9:34

22-Jun-09 9:34

Skippums wrote:
The lookup table idea is a great one for ASCII strings... I was only thinking in terms of unicode.

The Microsoft Unicode version of that function (wcspbrk) doesn't use a lookup table - it uses nested loops, same as the OP, in straight C rather than assembly language - so Unicode would probably yield comparable performance.

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

Ivan Ivanov 8322-Jun-09 11:28

22-Jun-09 11:28

"you are searching the same string for the same charset, so why not cache the result?"
- This is a good idea but I think it will make a major difference in my test code which tasts the came string and the same charset, and there aren't much cases like that in the real world. Smile | :)

but I'll try it - I don't have much options anyway!

"Perhaps it realized that your set of input characters is consecutive, and instead of iterating through them it tests each character against a range."
- I've tested it with mixed characters and letters - it's the same story, so I don't think that's the case - but I appreciate the idea!

"Perhaps the standard implementation starts from the end of the string and searches forward."
- I thought about that, it's quite possible. Why I didn't test it with mirrored string already? Big Grin | :-D

"Perhaps the compiler realized that the standard call to FindOneOf in your loop could be optimized away since you are not using any values of that method call except the final one"
- Well I looked at the disassembly so I can tell that's not the case Wink | ;)

- for each iteration of the test loop it calls CString::FindOneOf which then calls a bunch of other functions, somewhere in those functions I met call of "EnterCriticalSection" which blown my mind... ?! Big Grin | :-D

Otherwise you are quite right that standard functions are often optimized (as I mentioned about strlen) and the self-coded ones are not, especially those with __asm in them!

I think the lookup table has a potential!