|
I'll be a good boy and avoid more of my anti-STL rant. But I really do like the containers. Well, mostly even though I have found the ATL7 containers to produce smaller code with less syntactical mess.
But yes, I do like STL containers. I think... 
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Tim Smith wrote:
But yes, I do like STL containers. I think...
Yes you do, because you have realized the power of the dark side. Muhahahaha. 
--
Master, I'm so glad to feel your presence. But you don't seem to share my impatience. I relied upon you to break the silence. I cannot understand your reluctance.
Master, I feel so warm and I'm so happy, oh master.
Give me some more of the warm little beasts
I'm so fond of.
|
|
|
|
|
Since I am always interested in finding out if the STL method actually performs better, I love to test this stuff. There have been many cases where STL is faster. But this is another of many more cases where the "right" way isn't the faster way.
Base line, add ten elements and then clear: 40,813 MS
STL Method supplied by Funny and then clear: 40,781 MS
The "EVIL" hand written loop and then clear: 39,547 MS
At least this wasn't as bad as Scott Meyer's example in his "Why STL loops are better than hand written loops" article where HIS example ran 3 times slower than the handwritten loop.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
I left some extra code in the base line test. The real numbers are:
Base line, add ten elements and then clear: 38,843 MS
STL Method supplied by Funny and then clear: 40,157 MS
The "EVIL" hand written loop and then clear: 39,281 MS
These numbers seemed to be stable between multiple tests. The relationship was always maintained.
STL way added 1,314ms to the total time.
Hand written loop added 438ms to the total time.
Which means that the STL way is 3 times slower than the hand written loop. Even if you toss in 100 ms here and there for timing error, STL is still much slower.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Interesting. Thanks.
You have to admit the STL solution requires half the lines of code.
Kuphryn
|
|
|
|
|
Oh no argument there at all. But to me it all comes down to the trade-offs.
For me, the number of lines of code has never been an issue because it doesn't reflect on the complexity of the code. In this case, the STL version is very basic and easy to understand. So I give it high maintainability marks. However, I have seen many "1 line" STL statements that take 2 days to decode.
I just don't buy into this line that STL produces the "fastest" implementation. It just can't. STL produces the "most generic" implementation which might be fast. In my tests, STL tends to be much slower than doing things the old method. I have also seen little or no evidence that STL functors or algorithms reduce bugs.
If anything, I am here as a devils advocate. I want people to use STL for the right reasons. I use it myself and love it. But lately I have seen way too many people just reading from the "STL Talking Points" memo without ever questioning if the stuff is true.
I am in no way trying to say you are wrong to want to use STL's advanced features. I am just here to place a little seed of doubt so maybe we can add more people to the seemingly short list of people who question some of what is coming out of the standards committee.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
I am all eye, ear, and mind.
Kuphryn
|
|
|
|
|
Hi, I have a project in which I want to have multiple objects (in different VC projects) implement the same interface. Some of the code in my projects is already using the wonderful embedded IDL. The problem is, I don't seem to be able to add a standalone, project-wide .idl file and have it compiled too.
I'd hoped for some way for these interfaces to make it into the .tlb file but they are just ignored. Can you really not mix the embedded IDL and hard-coded IDL files? It seems crazy for my other projects to rely on an auto-generated file!
thanks in advance,
--
Simon Steele
Programmers Notepad - http://www.pnotepad.org/
|
|
|
|
|
Found the solution under "attributed programming" in MSDN:
[ importidl(idlfile) ];
or similar.
--
Simon Steele
Programmers Notepad - http://www.pnotepad.org/
|
|
|
|
|
Hi all.
I was reading WTL documentation: they say that a simple SDI application EXE takes 24 Kb if compiled with some NOWIN98 option.
Does this mean that the program runs on Win2000/XP only ?
Isn't it a limitation ?
The exe generated from my build (with default settings) takes 96 Kb.
Is it the normal size ?
Thanks in advance.
|
|
|
|
|
This is a linker option, which aligns chunks of the file on 4K boundaries by default, or on 512 byte boundaries with the /OPT:NOWIN98.
The larger file loads faster on Win98 with less swapping, according to Q235956, but I think the smaller one still runs.
Is your build a Debug or Release build? If Debug, then the file contains extra stuff.
Steve S
[This signature space available for rent]
|
|
|
|
|
I meant a Release build. I compiled the project with the default settings, as I downloaded it (only Release change, of course).
So the program will still run on Win98, won't it ?
The linker option is not restricted to WTL project, isn't it ?
|
|
|
|
|
puzzolino wrote:
So the program will still run on Win98, won't it ?
Yes it will still run.
puzzolino wrote:
The linker option is not restricted to WTL project, isn't it ?
Correct, you can just add the linker option in your linker options for your project settings. WTL does not change anything about the compiler or environment, it is simply a set of template classes to write windows programs in.
Build a man a fire, and he will be warm for a day
Light a man on fire, and he will be warm for the rest of his life!
|
|
|
|
|
Paul Watt (kilowatt) wrote:
Correct, you can just add the linker option in your linker options for your project settings. WTL does not change anything about the compiler or environment, it is simply a set of template classes to write windows programs in.
Of course, but why they compare MFC program size and WTL's with this option ?
Shouldn't they have applied this option to both projects before comparing ?
Mah...
Maybe they just wanted to upraise the latter....;P
|
|
|
|
|
This is the code from Dinkumware STL hash_map. This is also the same code in VC++.NET hash_map class.
This function gets called for every lookup. I find that the incoming key is compared with the object bothways. I mean
The comp function returns true for greater than. So the comparison is:
if a not greater than b
if b not greater than a,
then both are equal, return value.
Why not test for equality directly than go for this method? Is there any specific reason? Now, the string comparison is done twice to check for equality. The code does not seem to be in the overridable part of the hash_map.
Question: Is there any work around to prevent the comparison from running twice?
Note: I checked the CMapStringToString in MFC and it does just one comparison.
<br />
iterator lower_bound(const key_type& _Keyval)<br />
{ <br />
size_type _Bucket = _Hashval(_Keyval);<br />
iterator _Where;<br />
for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)<br />
if (!this->comp(this->_Kfn(*_Where), _Keyval))<br />
return (this->comp(_Keyval,<br />
this->_Kfn(*_Where)) ? end() : _Where);<br />
return (end());<br />
}<br />
modified 29-Aug-18 21:01pm.
|
|
|
|
|
By maintaining a sorted hash chain, if the compare fails greater than then either this entry matches or there is no chance that any later entries in the chain will match.
STLPort uses a equal_to system for hash_maps. But even looking at STLPort, there is some stuff in hash_map that is a little silly because of the need to be very generic. It will only bite you if your key compares are expensive (i.e. string compares).
Which system is better? You can't say since both systems have advantages. For example, the Dink system will average (depth/2+1) for successful searches while STLPort will average (depth/2). However, if you have a system where you will have many misses, Dink system will average (depth/2+1) while STLPort will average (depth). However, since Dink is using a sort chain, that will slow down inserts.
Once again proving my point that if performance is important, the general solution isn't the best.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
How would it be if I implemented a hash map that has a tree based map as buckets to handle collisions? The bucket would be a vector. This way, the worst case performance is the tree based map + the hash calculation. But, if there are no collissions, only one comparison is needed.
Does this sound right to implement my own hash_map. I am very disappointed with this Dinkumware hash_map. The standard map gives better performance, even when there are no collissions. I have a requirement where inserts and searches are very, very frequent. CMapStringToPtr was much better than this Dink hash_map; but now the project cannot have MFC.
- Thomas
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Could you use STLPort? It is starting to sound like their hash_map might work for you.
Are you recreating the hash map a lot? If not, then the auto-rehashing of STLPort's hash map would be a good feature. (For my specific needs, this one feature was a performance bottle neck)
Also, collisions don't have to be a bad thing. One of my most common speed improvements (other than removing the sometimes counter productive rehashing) is to try to make key compares very fast. For string based key compares I don't use strcmp. I store the length of string as part of the key. Thus prior to doing the actual byte compare of the string, I would compare then lengths. If they don't match, then the keys don't equal. If they do match you can use memcmp instead of strcmp for even more performance. If your keys are much more complicated than a simple string, then you can also use the computed hash value as a quick test. The important thing is to try to have a simple value that can act as a quick test to weed out the most possible slow key compares. This quick test should also be well distributed within the hash table.
Unfortunately, that speed improvement won't work for Dink's system since they want > instead of ==. If you decide to implement your own (but I would try STLPort first), I wouldn't over design it. Try a simple hash chain for collisions. Try a simple hash with a fixed width and a good quality hash generator. If you hash generator is good enough, your hash table doesn't even need to be sized by a prime. But primes work great for hash values based on such things as addresses. Try to improve your equality key test so that it is very fast. That is one thing I like about rolling your own simple hash map, you have total control over it and can design it specifically to meet your needs. For example, in my hash table for an atom table, I have the string stored in the same memory block as the rest of the hash support structure (which also means I used... MALLOC, oh horrors). This helps to prevent the CPU and L2 memory cache from having to access a ton of diverse pages. In my compiler's symbol table, I ended up storing everything including the hash in one long buffer. This allow me to quickly remove all local variables defined in a scope "{}" by restoring the hash table starting points and the size of the symbol table. 33 integer values copied with memcpy and one or a thousand local scope variables are removed in a flash. It is examples like this why I always preach that when appropriate people should never fear writing their own containers.
Ok, I am stopping now. I am starting to ramble.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Oh, and depending on the application, letting the hash table grow too wide can be counter productive. In the case of my compiler where I needed to save the hash state often, the optimal size was 256. But for overall performance, given that the symbol table search wasn't taking up much time, a hash width of 32 worked just fine (and my hash chains were getting 70+ entries deep ). I attribute the high performance to that simple length optimization in the key compare. The symbol table hardly ever made any false compares. (In fact, I think I will go add a counter to test just that.)
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Ok, here are some hard numbers from my compiler. This is with a symbol table where the hash is 32 entries wide. Each chain is known to average around 70 entries.
Total number of key compares: 58,028,872
Key compares rejected by hash/length test: 53,786,758
Slow key compares resulting in a match: 4,242,114
Slow key compares resulting in a failure: 0
As you can see, by testing the combination of the hash value and the string length, I was able to eliminate ALL false slow key compares.
Next I disabled the hash test for early key rejection. This resulted in 1,675,277 failed key compares.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Thank you very much for the info. I am downloading STLPort now. Also, I will try the length and memcmp instead of the strcmp that I am using now, as you suggested.
Thank you once again. I will keep you posted on my adventures with the hash_map.
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Cool , always learning ,I love CP, I don't known very well the hash algorithms, do you known some good resource where it explains the basic terminology and optimizations on the algorithms like this one on maps, besides the normal computer science books ?
Cheers,Joao Vaz
And if your dream is to care for your family, to put food on the table, to provide them with an education and a good home, then maybe suffering through an endless, pointless, boring job will seem to have purpose. And you will realize how even a rock can change the world, simply by remaining obstinately stationary.-Shog9
|
|
|
|
|
No. I make this stuff up on the fly, test it, and then hope I am not talking out of my arse.  (OMG, my secret is out.)
In all seriousness, that simple string optimization is from my work with the Forth language in the 80s. They had to deal with a wealth of symbols stored in a 4 wide hash table.
Darn it. I just was looking for a resource that I found last night that talked about a lot of hash optimizations. Can't seem to find the one I liked.
I did find this...
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html[^]
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Tim Smith wrote:
and then hope I am not talking out of my arse.
Experience, experience
Tim Smith wrote:
Forth language in the 80s.
 , I'm must admit that the 1st time that I've heard of Forth was here on CP when Valer Bocan posted his Forth compiler for .NET
Tim Smith wrote:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html[^]
Thanks, the article is nice and not too difficult to follow up
Cheers,Joao Vaz
And if your dream is to care for your family, to put food on the table, to provide them with an education and a good home, then maybe suffering through an endless, pointless, boring job will seem to have purpose. And you will realize how even a rock can change the world, simply by remaining obstinately stationary.-Shog9
|
|
|
|
|
One thing I noticed.
That article talked about rehashing to attempt to find an empty slot. When I say rehash, I mean using some heuristic to detect that the depth of the hash has become too large, thus triggering a resize of the hash table requiring all keys to be rehashed back into the larger table.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
