LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 01-06-2006, 10:52 AM   #1
gecoool
Member
 
Registered: Feb 2005
Location: Romania
Distribution: Fedora 2
Posts: 38

Rep: Reputation: 15
fast containers


Hello everyone. I need a very fast container, for an app which indexes words (web pages) (written in c++/linux, stl containers). I used maps, which are very popular (recomended on programming forums), then i moved to hash_map which brought significant speed gain. However when my hash_maps are growing, as the program indexes more words, the program slows down considerably. My questions:

1. Is there any other container faster than hash_map ?
2. Using other hashing function that the default one provided by hash_map (used for hashing strings, as keys for my hash_map), could I expect significant speed improvement ? (i.e. I tried SuperFastHash, which I found it @ http://www.azillionmonkeys.com/qed/hash.html).



Thank you people for your time !
 
Old 01-07-2006, 02:45 PM   #2
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
You're assuming that the program is slowing down because the algorithm your particular hash_map is using doesn't scale well. I agree - that's probably the case.

But maybe the problem is insufficient RAM: as you add more strings, your program uses lots more memory ... and at some point, you begin swapping. And the program slows because of the SWAPPING, not because of the algorithm.

You could easily verify it by running "swapon -s" and/or "vmstat" when your program slows down.

Just a thought...
 
Old 01-08-2006, 06:43 AM   #3
gecoool
Member
 
Registered: Feb 2005
Location: Romania
Distribution: Fedora 2
Posts: 38

Original Poster
Rep: Reputation: 15
Thank you for time !

I really don't think that's the case: my app is running on dual processor system with plenty of RAM (1Gb Ram). I tried to run my app while no other appz/servers where running , but I get the very same behavior ;-(
 
Old 01-08-2006, 06:18 PM   #4
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
A hash_map is only as good as its hash. As you add more data the likelihood of a collision increases. I don't know what the default hash function is for char *, but knowing that the inputs are (case insensitive?) words, you can probably improve it.

As a guess I would try a huffman encoded version of the string, using the frequencies of letters in dictionary words. But with some thought you can probably do much better.
 
Old 02-02-2006, 03:55 AM   #5
gecoool
Member
 
Registered: Feb 2005
Location: Romania
Distribution: Fedora 2
Posts: 38

Original Poster
Rep: Reputation: 15
None taken. I think it was funny ;-). I asked myself too, about that default hash on char *, which caused me a lot of head eachs when i first tried to use hash_map on std::string ;-)
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
FAST (Mega fast Mirror) SUSE 10 beta 4 download 1kyle Suse/Novell 2 09-07-2005 11:13 AM
Slamd64 is FAST FAST !!! SML Slackware 10 05-03-2005 06:36 AM
KDE 3.4 Beta 1 - Fast, Fast, very nice linchat Suse/Novell 0 01-26-2005 12:42 AM
how to free linked list containers? rgiggs Programming 3 07-30-2004 02:24 PM
stl containers champ Programming 2 04-09-2003 06:27 AM


All times are GMT -5. The time now is 02:36 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration