How to use a 5 or 6 bit integer in Python?

[Glen Wheeler]

Hello all,

My program uses many millions of integers, and Python is allocating
way too much memory for these. I can't have the performance hit by
using disk, so I figured I'd write a C extension to define a new type.
Problem is, my C knowledge is years old and regardless of my
attempts distutils will not recognise my installation of the MS
compiler.
I am thinking, is there any easier way to use a 5 or 6 bit integer
in python? Even a regular 8-bit would be fine. I only need to
represent either 32 or 64 distinct numbers.

thanks,
Glen

[Bengt Richter]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 11:42:49 +1100, Glen Wheeler <adsl5lcq@tpg.c om.au> wrote:
[color=blue]
>
> Hello all,
>
> My program uses many millions of integers, and Python is allocating
>way too much memory for these. I can't have the performance hit by
>using disk, so I figured I'd write a C extension to define a new type.
> Problem is, my C knowledge is years old and regardless of my
>attempts distutils will not recognise my installation of the MS
>compiler.
> I am thinking, is there any easier way to use a 5 or 6 bit integer
>in python? Even a regular 8-bit would be fine. I only need to
>represent either 32 or 64 distinct numbers.
>[/color]
You can store them efficiently in an array, e.g., for unsigned bytes
(or 'b' in place of 'B' for signed):
[color=blue][color=green][color=darkred]
>>> import array
>>> bytes = array.array('B' , range(10))
>>> bytes[/color][/color][/color]
array('B', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])[color=blue][color=green][color=darkred]
>>> bytes[3][/color][/color][/color]
3

We can only speculate on further help, until you tell us what you are doing ;-)

Regards,
Bengt Richter

[Paul Rubin]

Re: How to use a 5 or 6 bit integer in Python?

Glen Wheeler <adsl5lcq@tpg.c om.au> writes:[color=blue]
> My program uses many millions of integers, and Python is allocating
> way too much memory for these. I can't have the performance hit by
> using disk, so I figured I'd write a C extension to define a new type.
> Problem is, my C knowledge is years old and regardless of my
> attempts distutils will not recognise my installation of the MS
> compiler.
> I am thinking, is there any easier way to use a 5 or 6 bit integer
> in python? Even a regular 8-bit would be fine. I only need to
> represent either 32 or 64 distinct numbers.[/color]

Look at the docs for the array module.

[Rainer Deyke]

Re: How to use a 5 or 6 bit integer in Python?

Glen Wheeler wrote:[color=blue]
> Hello all,
>
> My program uses many millions of integers, and Python is allocating
> way too much memory for these. I can't have the performance hit by
> using disk, so I figured I'd write a C extension to define a new type.
> Problem is, my C knowledge is years old and regardless of my
> attempts distutils will not recognise my installation of the MS
> compiler.
> I am thinking, is there any easier way to use a 5 or 6 bit integer
> in python? Even a regular 8-bit would be fine. I only need to
> represent either 32 or 64 distinct numbers.[/color]

You're trying to solve the wrong problem. Python caches small integers, so
you've only got a very small number of distinct integer objects. This is a
good thing, because each Python object has a eight byte overhead.
Introducing a new type wouldn't result in any memory savings.

The real overhead comes from the references to those objects. Each
reference is four bytes (on 32 bit computers), and there is no way to
decrease this. Your best option is to use high level objects that contain
many integers internally but don't store them as individual Python
references. The array module is one choice, Numarray is another. If
immutability isn't an issue, you could even use strings (with each character
treated as an eight bit integer).


--
Rainer Deyke - rainerd@eldwood .com - http://eldwood.com

[Ben Finney]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 11:42:49 +1100, Glen Wheeler wrote:[color=blue]
> My program uses many millions of integers, and Python is allocating
> way too much memory for these.[/color]

How have you measured this? As pointed out by others, Python doesn't
have duplicate occurrences of identical integers; it refers to the same
object multiple times.

Given this, I'm curious how you've measured the memory usage caused by
your program using millions of integers, and why you think reducing the
size of those integers will help significantly.

--
\ "I like to fill my bathtub up with water, then turn the shower |
`\ on and pretend I'm in a submarine that's been hit." -- Steven |
_o__) Wright |
Ben Finney <http://bignose.squidly .org/>

[Glen Wheeler]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 03:17:36 GMT, "Rainer Deyke" <rainerd@eldwoo d.com>
wrote:
[color=blue]
>You're trying to solve the wrong problem. Python caches small integers, so
>you've only got a very small number of distinct integer objects. This is a
>good thing, because each Python object has a eight byte overhead.
>Introducing a new type wouldn't result in any memory savings.
>[/color]

Thanks. I had thought as much, but was not totally sure.
[color=blue]
>The real overhead comes from the references to those objects. Each
>reference is four bytes (on 32 bit computers), and there is no way to
>decrease this. Your best option is to use high level objects that contain
>many integers internally but don't store them as individual Python
>references. The array module is one choice, Numarray is another. If
>immutability isn't an issue, you could even use strings (with each character
>treated as an eight bit integer).[/color]

So the references to each integer is what causes the massive
overhead.
I've read up on Numarray and the array module in the docs, but
didn't see how I could adapt my current program to use these modules
because of how my data is currently organised.
I have one constantly changing dict with many millions of keys
(tuples of ints) which in turn associates itself with a tuple of ints
and two more dicts.
Every single container type contains only integers. Am I correct in
assuming that an array cannot be used as a key for a dictionary? As
they are mutable?

Thanks for your help,
Glen

[Glen Wheeler]

Re: How to use a 5 or 6 bit integer in Python?

On 19 Dec 2003 13:59:44 +1050, Ben Finney
<bignose-hates-spam@and-benfinney-does-too.id.au> wrote:
[color=blue]
>On Fri, 19 Dec 2003 11:42:49 +1100, Glen Wheeler wrote:[color=green]
>> My program uses many millions of integers, and Python is allocating
>> way too much memory for these.[/color]
>
>How have you measured this? As pointed out by others, Python doesn't
>have duplicate occurrences of identical integers; it refers to the same
>object multiple times.
>
>Given this, I'm curious how you've measured the memory usage caused by
>your program using millions of integers, and why you think reducing the
>size of those integers will help significantly.[/color]

I realise now that I was wrong in assuming this. However, Python
does use more memory than it needs to to store the data I'm
manipulating. This is probably caused by their container types,
dictionaries and tuples, however.
Reducing the amount of memory allocated by any method is my goal
right now, along with increasing the speed at which my program runs.
I'm using one dictionary to store all of the data, with tuples of
ints as keys and a tuple as the data associated with each key. The
data tuples contain a few ints and two more dictionaries.
Can you think of a way to reduce the memory used here?

Thanks,
Glen

[Bengt Richter]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 14:30:23 +1100, Glen Wheeler <adsl5lcq@tpg.c om.au> wrote:
[color=blue]
>On Fri, 19 Dec 2003 03:17:36 GMT, "Rainer Deyke" <rainerd@eldwoo d.com>
>wrote:
>[color=green]
>>You're trying to solve the wrong problem. Python caches small integers, so
>>you've only got a very small number of distinct integer objects. This is a
>>good thing, because each Python object has a eight byte overhead.
>>Introducing a new type wouldn't result in any memory savings.
>>[/color]
>
> Thanks. I had thought as much, but was not totally sure.
>[color=green]
>>The real overhead comes from the references to those objects. Each
>>reference is four bytes (on 32 bit computers), and there is no way to
>>decrease this. Your best option is to use high level objects that contain
>>many integers internally but don't store them as individual Python
>>references. The array module is one choice, Numarray is another. If
>>immutabilit y isn't an issue, you could even use strings (with each character
>>treated as an eight bit integer).[/color]
>
> So the references to each integer is what causes the massive
>overhead.
> I've read up on Numarray and the array module in the docs, but
>didn't see how I could adapt my current program to use these modules
>because of how my data is currently organised.
> I have one constantly changing dict with many millions of keys
>(tuples of ints) which in turn associates itself with a tuple of ints
>and two more dicts.
> Every single container type contains only integers. Am I correct in
>assuming that an array cannot be used as a key for a dictionary? As
>they are mutable?[/color]
Yes, but you might be able to do better than tuples, depending on what
the ordering means and whether the same number can repeat in a tuple, etc.

If we can tease out a little more about your problem, maybe we can help better ;-)
E.g., how do your tuple-keys come into being and how many times are they re-used?
If there is no nesting, you could create a string key just by ''.join([chr(el) for el in tup])
which wouldn't be as compact as a compressed bit string, but would be smaller than the tuple.
If you were lucky, a change could gain you both time and space.

I'm curious what your dicts and their int tuples represent in the real world ;-)

Regards,
Bengt Richter

[Rainer Deyke]

Re: How to use a 5 or 6 bit integer in Python?

Glen Wheeler wrote:[color=blue]
> I have one constantly changing dict with many millions of keys
> (tuples of ints) which in turn associates itself with a tuple of ints
> and two more dicts.[/color]

That makes things a bit harder. I expect that the big dict itself requires
at least sixteen bytes per entry. How big are your tuples? How big are the
dicts in the data tuples? What data do they contain? Are any of the tuples
or dicts shared?

Encoding the key tuples as strings is easy (''.join([chr(x) for x in
the_tuple]). Encoding the ints in the data tuples is just as easy. I'm not
sure if those are enough to solve your problem.


--
Rainer Deyke - rainerd@eldwood .com - http://eldwood.com

[Gabriel Genellina]

Re: How to use a 5 or 6 bit integer in Python?

At 19/12/2003 14:30, you wrote:
[color=blue]
> I have one constantly changing dict with many millions of keys
>(tuples of ints) which in turn associates itself with a tuple of ints
>and two more dicts.[/color]

How big are the integers? If 16 bits for each are enough, you could replace
those 2-elem tuples with an plain integer: (a,b) -> a<<16 | b
You dont waste space from a tuple object (and its construction time) plus
two references for each dictionary key used, but you eventually create many
more integer instances. And there is a penalty accessing the dictionary
since you have to compute the key.


Gabriel Genellina
Softlab SRL

[Glen Wheeler]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 06:27:59 GMT, "Rainer Deyke" <rainerd@eldwoo d.com>
wrote:
[color=blue]
>Glen Wheeler wrote:[color=green]
>> I have one constantly changing dict with many millions of keys
>> (tuples of ints) which in turn associates itself with a tuple of ints
>> and two more dicts.[/color]
>
>That makes things a bit harder. I expect that the big dict itself requires
>at least sixteen bytes per entry. How big are your tuples?[/color]

The key tuples, for the final calculation will range from 1 element
to 64 elements, with the majority at around 40-50 elements in size.
[color=blue]
> How big are the dicts in the data tuples? What data do they contain?[/color]

For the first dict: Increasingly smaller as the calculation
continues (i.e. as the key for that entry increases). Initially they
will have 64 keys (integers) with each integer having a 6-element
tuple of integers as it's data type. All integers are from 0-63.
For the second dict: Trivially small, with a maximum of 32
elements, starts at 0 and an average of around 7. Keys are kept as
integers from 0-63 and data ranges from -1-30, but the average case
will see the data at 7, as a single integer.
[color=blue]
> Are any of the tuples or dicts shared?
>[/color]

Unfortunately, no. This would be a major speedup for my program as
copying the dictionaries and tuples takes not only alot of memory but
alot of time too.
But the truth is that I need these to be unique on a key-by-key
basis (context from the big dict) so I can't see any way around it.
[color=blue]
>Encoding the key tuples as strings is easy (''.join([chr(x) for x in
>the_tuple]). Encoding the ints in the data tuples is just as easy. I'm not
>sure if those are enough to solve your problem.[/color]

I'll be sure to do this. Will it increase the hash speed for the
big dictionary significantly? Will lookup times or memory storage
requirements decrease?

Thanks,
Glen

[Borcis]

Re: How to use a 5 or 6 bit integer in Python?

Glen Wheeler wrote:
[color=blue]
> I'm using one dictionary to store all of the data, with tuples of
> ints as keys and a tuple as the data associated with each key. The
> data tuples contain a few ints and two more dictionaries.
> Can you think of a way to reduce the memory used here?[/color]

What's the length of the key tuples, and are there bounds on the
component ints ? Is the number of ints in the data tuples fixed ? What's
in the subdictionnarie s, typically ? "millions of 5 bit integers" hints
of the possibility of a radical change of representation, but a radical
change of representation can only be devised if we know what's stable
- the task.

[Rainer Deyke]

Re: How to use a 5 or 6 bit integer in Python?

Glen Wheeler wrote:[color=blue]
> I'll be sure to do this. Will it increase the hash speed for the
> big dictionary significantly? Will lookup times or memory storage
> requirements decrease?[/color]

Using strings instead of tuples of integers should decrease memory usage. A
character in a string is stored as a single byte, whereas each tuple element
needs four bytes.


--
Rainer Deyke - rainerd@eldwood .com - http://eldwood.com

[Derrick 'dman' Hudson]

tuning memory and time usage (was: Re: How to use a 5 or 6 bit integer in Python?)

Glen :

On Fri, 19 Dec 2003 14:30:23 +1100, Glen Wheeler wrote:
[color=blue]
> I've read up on Numarray and the array module in the docs, but
> didn't see how I could adapt my current program to use these modules
> because of how my data is currently organised.[/color]

You may need to reorganize the data in order to save space!
[color=blue]
> I have one constantly changing dict with many millions of keys
> (tuples of ints) which in turn associates itself with a tuple of ints
> and two more dicts.[/color]

If you state the actual task and computation you are performing then
people can suggest alternate data structures and algorithms. Simply
describing your current data structure leaves people shooting in the
dark trying to suggest alternate ways of storing the data.

Usually time and space (memory) are mutually exclusive tradeoffs --
less computation requires more storage, less storage requires more
computation. However, there are cases where poor choice in data
structure and/or algorithm can allow a restructuring to improve both
speed and memory use.

In order to construct and evaluate data structure and algorithm
suitability a a concrete understanding of what task needs to be
performed by the program and what sort of data will be handled is
essential.

Presently you, Glen, are the only one with this knowledge of the task
and problem space. Share that knowledge with the group and the group
will then be capable of better assisting you.

-D

--
A mouse is a device used to point at the xterm you want to type in.
--Kim Alm, a.s.r

www: http://dman13.dyndns.org/~dman/ jabber: dman@dman13.dyn dns.org

[Glen Wheeler]

Re: How to use a 5 or 6 bit integer in Python?

On Fri, 19 Dec 2003 14:21:16 +0100, Borcis <borcis@users.c h> wrote:
[color=blue]
>Glen Wheeler wrote:
>[color=green]
>> I'm using one dictionary to store all of the data, with tuples of
>> ints as keys and a tuple as the data associated with each key. The
>> data tuples contain a few ints and two more dictionaries.
>> Can you think of a way to reduce the memory used here?[/color]
>
>What's the length of the key tuples, and are there bounds on the
>component ints ?[/color]

Component ints will either be 0-63 or 0-31. In a single run of the
program, this will not change throughout.
The key tuples range in length from 1-64, depending on at what stage
the program is currently at. Every tuple will have the same length at
some point; the greatest possible distance in length from any two
tuples is 1.
[color=blue]
> Is the number of ints in the data tuples fixed ?[/color]

Yes, there are always two ints, and another tuple of ints. One int
is arbitrary, and can be in the thousands but not much higher.
Another int is from 0-5. The tuple of ints is less than 6 long and
will contain either 0-63 or 0-31, depending on the parameters given to
the program at run time.
[color=blue]
> What's in the subdictionnarie s, typically ? "millions of 5 bit integers" hints
>of the possibility of a radical change of representation, but a radical
>change of representation can only be devised if we know what's stable
>- the task.[/color]

Well, the subdictionaries contents are described in another reply
written by me in this same thread. There are indeed many millions of
integers beign stored at any one time, or at least many millions of
references to these integers.
You are saying that to save any amount of memory something in the
large dictionary must be constant? I am sure everything in there is
dynamic in nature, i.e. will change with each iteration over the keys
in the large dictionary.

--
Glen