473,574 Members | 2,203 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Reducing memory overhead for dictionaries by removing precomputed hash

Forgive me if this has already been discussed, but it seems to me that
one could reduce the memory usage of dictionaries by 2/3 by removing
the precomputed hash in each bucket.

Since Dictionaries only allow immutable objects as keys, one could move
the precomputed hash into the keys.

* Strings are probably the most popular keys for dictionaries and they
already cache the hash (hmm that almost rhymes).
* Numbers are trivial to hash.
* For Tuples one could add a member to cache the hash.

So why store the hash? I imagine it makes rebuilding the dictionary a
bit quicker, since I guess you can avoid some comparisions since you
know there are no duplicates. haven't looked at the code to see if it
does that tho.

and collision chains are possibly a bit quicker to traverse, tho I
think python uses a mask instead of a mod by prime, so hash keys with
the same low bits will collide, so collisions might be more common, but
that's possibly fixable by using a congruential hash, but that's all
black magic to me.

-Kirat

Apr 18 '06 #1
0 913

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
1601
by: Thomas Rast | last post by:
Hello everyone My scenario is somewhat involved, so if you're in a hurry, here's an abstract: I have a daemon that needs about 80MB of RAM to build its internal data structures, but can pack them to 20MB for the rest of its lifetime. The other 60MB are never returned to the operating system. I've thought of building and packing the...
1
2907
by: DJTB | last post by:
zodb-dev@zope.org] Hi, I'm having problems storing large amounts of objects in a ZODB. After committing changes to the database, elements are not cleared from memory. Since the number of objects I'd like to store in the ZODB is too large to fit in RAM, my program gets killed with signal 11 or signal 9... Below a minimal working (or...
16
3034
by: Rich S | last post by:
Or just loosing it? I have a small c++ app which generates millions combinations of bitset class objects and adds them to a STL map. (on a side thanks to all who responded to my earlier posting about increasing the programs speed) Anyway, I calculate my bitset class object size to be 8 bytes and when I run this in debug mode I can...
4
2335
by: Evangelista Sami | last post by:
hello all i am implementing an application in which a large number of (char *) is stored into a hash table structure. As there may be collisions, each (char *) inserted into my hash table is put into an array. here is the definition of my hash table : typedef struct { short size;
2
13364
by: Martin | last post by:
I already know some techniques for writing small footprint software, but now I need to really squeeze the software I'm writing into a small space (embedded software). Is there a good web page that discsuesses techniques for this? A good book? /Martin
10
399
by: Segfahlt | last post by:
I have a fairly simple C# program that just needs to open up a fixed width file, convert each record to tab delimited and append a field to the end of it. The input files are between 300M and 600M. I've tried every memory conservation trick I know in my conversion program, and a bunch I picked up from reading some of the MSDN C# blogs, but...
4
988
by: xarnaudx | last post by:
hi, i've just a simple question: what are the time complexities of inserting / removing / checking if an element is present in 1) a list and 2) a dictionary? does anybody know? thanks
3
1595
by: Xiaoning He | last post by:
hi currently i'm using a crawler called larbin to get some pages, it hashes each url to an integer. This is not a good method comparing to md5, however it's enough for me. Currently i set the hash value to be a 31-bit integer, which is used to be the index of a bit string in memory, thus needs 256MB memory. i have 4GB+ free memory, so my...
14
1801
by: cnb | last post by:
Are dictionaries the same as hashtables?
0
7803
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
1
7810
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8096
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6451
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5618
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5299
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3749
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2240
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
1056
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.