processing a Very Large file

[DJTB]

Hi,

I'm trying to manually parse a dataset stored in a file. The data should be
converted into Python objects.

Here is an example of a single line of a (small) dataset:

3 13 17 19 -626177023 -1688330994 -834622062 -409108332 297174549 955187488
589884464 -1547848504 857311165 585616830 -749910209 194940864 -1102778558
-1282985276 -1220931512 792256075 -340699912 1496177106 1760327384
-1068195107 95705193 1286147818 -416474772 745439854 1932457456 -1266423822
-1150051085 1359928308 129778935 1235905400 532121853

The first integer specifies the length of a tuple object. In this case, the
tuple has three element: (13, 17, 19)
The other values (-626177023 to 532121853) are elements of a Set.

I use the following code to process a file:
from time import time
from sets import Set
from string import split
file = 'pathtable_ht.dat'
result = []
start_time = time ()
f=open(file,'r')
for line in f:
splitres = line.split()
tuple_size = int(splitres[0])+1
path_tuple = tuple(splitres[1:tuple_size])
conflicts = Set(map(int,splitres[tuple_size:-1]))
# do something with 'path_tuple' and 'conflicts'
# ... do some processing ...
result.append(( path_tuple, conflicts))

f.close()
print time() - start_time
The elements (integer objects) in these Sets are being shared between the
sets, in fact, there are as many distinct element as there are lines in the
file (eg 1000 lines -> 1000 distinct set elements). AFAIK, the elements are
stored only once and each Set contains a pointer to the actual object

This works fine with relatively small datasets, but it doesn't work at all
with large datasets (4500 lines, 45000 chars per line).

After a few seconds of loading, all main memory is consumed by the Python
process and the computer starts swapping. After a few more seconds, CPU
usage drops from 99% to 1% and all swap memory is consumed:

Mem: 386540k total, 380848k used, 4692k free, 796k buffers
Swap: 562232k total, 562232k used, 0k free, 27416k cached

At this point, my computer becomes unusable.

I'd like to know if I should buy some more memory (a few GB?) or if it is
possible to make my code more memory efficient.

Thanks in advance,
Stan.

[Tim Peters]

[DJTB]

I'm trying to manually parse a dataset stored in a file. The data should be
converted into Python objects.

Here is an example of a single line of a (small) dataset:

3 13 17 19 -626177023 -1688330994 -834622062 -409108332 297174549 955187488 589884464 -1547848504 857311165 585616830 -749910209 194940864 -1102778558 -1282985276 -1220931512 792256075 -340699912 1496177106 1760327384 -1068195107 95705193 1286147818 -416474772 745439854 1932457456 -1266423822 -1150051085 1359928308 129778935 1235905400 532121853

The first integer specifies the length of a tuple object. In this case, the
tuple has three element: (13, 17, 19)
The other values (-626177023 to 532121853) are elements of a Set.

I use the following code to process a file:

from time import time
from sets import Set
from string import split
Note that you don't use string.split later.
file = 'pathtable_ht.dat'
result = []
start_time = time ()
f=open(file,'r')
for line in f:
splitres = line.split()
Since they're all integers, may as well:

splitres = map(int, line.split())

here and skip repeated int() calls later.
tuple_size = int(splitres[0])+1
path_tuple = tuple(splitres[1:tuple_size])
conflicts = Set(map(int,splitres[tuple_size:-1]))
Do you really mean to throw away the last value on the line? That is,
why is the slice here [tuple_size:-1] rather than [tuple_size:]?
# do something with 'path_tuple' and 'conflicts'
# ... do some processing ...
result.append(( path_tuple, conflicts))

f.close()
print time() - start_time

The elements (integer objects) in these Sets are being shared between the
sets, in fact, there are as many distinct element as there are lines in the
file (eg 1000 lines -> 1000 distinct set elements). AFAIK, the elements are
stored only once and each Set contains a pointer to the actual object
Only "small" integers are stored uniquely; e.g., these aren't:

100 * 100 is 100 * 100 False int("12345") is int("12345") False

You could manually do something akin to Python's "string interning" to
store ints uniquely, like:

int_table = {}
def uniqueint(i):
return int_table.setdefault(i, i)

Then, e.g.,
uniqueint(100 * 100) is uniqueint(100 * 100) True uniqueint(int("12345")) is uniqueint(int("12345"))

True

Doing Set(map(uniqueint, etc)) would then feed truly shared int
(and/or long) objects to the Set constructor.
This works fine with relatively small datasets, but it doesn't work at all
with large datasets (4500 lines, 45000 chars per line).
Well, chars/line doesn't mean anything to us. Knowing # of set
elements/line might help. Say there are 4500 per line. Then you've
got about 20 million integers. That will consume at least several 100
MB if you don't work to share duplicates. But if you do so work, it
should cut the memory burden by a factor of thousands.
After a few seconds of loading, all main memory is consumed by the Python
process and the computer starts swapping. After a few more seconds, CPU
usage drops from 99% to 1% and all swap memory is consumed:

Mem: 386540k total, 380848k used, 4692k free, 796k buffers
Swap: 562232k total, 562232k used, 0k free, 27416k cached

At this point, my computer becomes unusable.

I'd like to know if I should buy some more memory (a few GB?) or if it is
possible to make my code more memory efficient.

See above for the latter. If you have a 32-bit processor, you won't
be able to _address_ more than a few GB anyway. Still, 384MB of RAM
is on the light side these days <wink>.

[Steve M]

I'm surprised you didn't recommend to use ZODB. Seems like an ideal way
to manage this large amount of data as a collection of Python objects...

[Gregory Bond]

DJTB wrote:

Hi,

I'm trying to manually parse a dataset stored in a file. The data should be
converted into Python objects.

In addition to what the others have mentioned, this sort of problem is
pretty easy to do with a C coded extension type, if you have (or can
buy/borrow) any C skills. The result is waaaay more efficient in time
and memory, particularly if you actually don't wind up looking at most
elements.

But Robert's solution (use iterators/generators rather than store them
all in a list) is probably best/quickest if that is possible for your app.

[DJTB]

Tim Peters wrote:

tuple_size = int(splitres[0])+1
path_tuple = tuple(splitres[1:tuple_size])
conflicts = Set(map(int,splitres[tuple_size:-1]))
Do you really mean to throw away the last value on the line? That is,
why is the slice here [tuple_size:-1] rather than [tuple_size:]?

Thanks, you saved me from another bug-hunting hell...
(In a previous test version, split returned a '\n' as the last item in the
list...)

You could manually do something akin to Python's "string interning" to
store ints uniquely, like:

int_table = {}
def uniqueint(i):
return int_table.setdefault(i, i)

Then, e.g.,

uniqueint(100 * 100) is uniqueint(100 * 100) True uniqueint(int("12345")) is uniqueint(int("12345"))

True

Doing Set(map(uniqueint, etc)) would then feed truly shared int
(and/or long) objects to the Set constructor.

I've implemented this and it does seem to work, thanks.

Stan.