[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Tim Peters  added the comment:

Thanks, Terry!  Based on your latest results, "quadratic time" isn't plausible 
here anymore, so I'm closing this.  Nasty cache effects certainly played a 
role, but they were just a flea on the dog ;-)

--
resolution:  -> fixed
stage: commit review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Terry J. Reedy]

Terry J. Reedy  added the comment:

I reran the code in msg312188.  Ints as before, string deletion +- linear up to 
100 million, much better than before.

millions   old stringsnew strings
of items  create delete  create delete
   4   1.55.36 1.7.38
   8   3.18.76 3.6.78
  16   6.48   1.80 7.3   1.71
  32  13.65.5614.8   3.8
  64  28 19   30 8.4
 100  56 80   5014.3

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Tim Peters  added the comment:

Raymond, please read my very recent comment one above yours.  A (overall) 
quadratic-time algorithm (O(A**2) where A is the number of arenas) in 
obmalloc.c is (to my eyes) probably the _primary_ cause of the sloth here.  
That's been fixed for 3.8, but I don't have enough RAM even to run Terry's test 
code to confirm it.

I can confirm that there's no quadratic-time behavior anymore deleting large 
sets of strings, but only until I run out of RAM.  Neither is the behavior 
linear, but it's much closer to linear than quadratic now.

If someone with more RAM can confirm this for larger sets, then fine by me if 
this is closed again.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Can we close this now?  ISTM the issue has less to do with sets and more to do 
with memory allocation quirks and that on modern CPUs random memory accesses 
are slower than sequential memory accesses.  It is not a bug that sets are 
unordered collections that iterate over elements in a difference order than 
they were inserted.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Change by Tim Peters :


--
stage: resolved -> commit review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Tim Peters  added the comment:

Looks likely that the _major_ cause of the quadratic-time delete behavior was 
due to that obmalloc used a linear-time method to keep its linked list of 
usable arenas sorted in order of number of free pools.  When a pool became 
unused, its arena's count of free pools increased by one, and then order was 
restored by moving the arena "to the right" in the linked list, one slot at a 
time.

When there were only a few hundred arenas, nobody noticed.  But programs with 
thousands of arenas could suffer very noticeable sloth, and programs with 
hundreds of thousands could appear to hang (could require days to complete 
deleting).

This was fixed in issue #37029, using a constant-time method to restore sorted 
order, scheduled for release in Python 3.8.

--
stage:  -> resolved
versions: +Python 3.8 -Python 3.9

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Inada Naoki]

Change by Inada Naoki :


--
resolution: wont fix -> 
stage: resolved -> 
status: closed -> open
versions: +Python 3.9 -Python 3.7, Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Inada Naoki]

Inada Naoki  added the comment:

I thought compact set implementation similar to dict sicne Python 3.6 may fix 
this issue.
But as discussion with Raymond on Python-Dev ML, I conclude the merits of 
compact implementation is not significant enough.
I abandoned compact set branch.

Now I don't have any idea to fix this issue in foreseeable future.
Please use dict instead.

--
resolution:  -> wont fix
stage: needs patch -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[INADA Naoki]

INADA Naoki  added the comment:

@Luis, would you try dict instead of set?  It's little larger than set, but 
delete elements by insertion order.

But I don't think builtin data structure can be optimized for such workload.
Maybe, LMBD[1] or some other KVS can help you.

[1]: https://lmdb.readthedocs.io/en/release/

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Marc-Andre Lemburg]

Marc-Andre Lemburg  added the comment:

Reminds of some experiments someone did a while ago as part of the
GIL removal attempts where the ref count integers are all kept in a
separate array. The intent there was to be able to do locking on
a single array rather than on individual decref cells.

This would solve the issue with having to jump around in memory
to decref all objects, but I'm not sure whether the overall win
would be a lot, since deallocation of the memory blocks typically
requires accessing the block itself as well (to update the block
chain list pointers), unless the memory allocator uses some
smart cache local block management as well (I believe that pymalloc
does, but could be wrong).

In any case, this sounds like a fun experiment for a GSoC student.
Perhaps the PSF could donate an AWS EC2 instance with enough RAM to
do the experiments.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Luis Pedro Coelho]

Luis Pedro Coelho  added the comment:

I think some of this conversation is going off-topic, but there is no 
disk-swapping in my case.

I realize ours is not a typical setup, but our normal machines have 256GB of 
RAM and the "big memory" compute nodes are >=1TB. Normally, swap is outright 
disabled.

This really is an impressive case study on how much difference cache-locality 
can make.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[INADA Naoki]

INADA Naoki  added the comment:

> Dict is (surprisingly) little smaller than set.

I'm sorry, I was wrong.
dict is smaller than set only when len(d) is small. (typical case for namespace 
dict)

In case of massive keys, dict is larger than set.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[INADA Naoki]

INADA Naoki  added the comment:

One possible advice; try dict instead of set.
Dict is (surprisingly) little smaller than set.
And dict cleans items in insertion order when the dict is deleted.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Tim Peters  added the comment:

> Surprisingly, deleting a very large set takes much longer than creating it.

Luis, that's not surprising ;-)  When you create it, it's mostly the case that 
there's a vast chunk of raw memory from which many pieces are passed out in 
address order (to hold all the newly created Python objects).  Memory access is 
thus mostly sequential.  But when you delete it, that vast chunk of once-raw 
memory is visited in essentially random order (string hashes impose a 
pseudo-random order on where (pointers to) string objects are stored within a 
set's vector), defeating all the hardware features that greatly benefit from 
sequential access.

More precisely, the set's internal vector is visited sequentially during 
deletion, but the string objects the pointers point _at_ are all over the 
place.  Even if nothing is swapped to disk, it's likely that visiting a string 
object during deletion will miss on all cache levels, falling back to (much 
slower) RAM.  Note that all the string objects must be visited during set 
deletion, in order to decrement their reference counts.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Terry J. Reedy]

Terry J. Reedy  added the comment:

Luís, what you really need for the problem you outline is an immutable set with 
one operation, 'in', aside from create and delete.  If specialized to strings 
only, it could internally stores only character sequences, rather than Python 
objects.  I suspect someone has written such a class (in C), but did not find 
anything on pypi.python.org.

Lacking that, the following experiment suggests that you might be able to 
restore near O(n) time by partitioning the set of keys into a collection of 
sets.  My 16M set took 6.48 and 1.80 seconds.  Times 4 is 25.9 and 7.2.  My 64M 
set took 28 and 19 seconds, but 4 16M sets take 26.3 and 7.5 seconds, only 
about 5% more than the x4 target.

print(timeit.Timer(
's = [{str(n) for n in range(i*100, (i+16)*100)}'
' for i in (0, 16, 32, 48)]')
  .timeit(number=1))
print(timeit.Timer(
'del s',
's = [{str(n) for n in range(i*100, (i+16)*100)}'
' for i in (0, 16, 32, 48)]')
  .timeit(number=1))

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Thanks for the info.  Here is what I surmise from the data.  

* The shape of the curve matches the expected memory latency curve for random 
memory accesses for a given working set size.  The graph of your measurements 
looks similar in shape to this one:  
https://www.extremetech.com/wp-content/uploads/2014/08/latency.png

*  The last line of the measurements has N=1,500,000,000.   That would give an 
approx 70GB setobject that refers to another 100Gb (or more) of strings.  
Unless you are working with an extraordinary machine, most of that data will 
have been swapped to disk.

* Dividing the 1,500,000,000 elements by the time of 25,068 seconds gives about 
60,000 deletions per second.  This number coincides nicely with the random 
access performance of a typical SSD rated at  50,000 IOPs.

If this reasoning is sound, all it proves is that random accesses to virtual 
memory are limited by the speed of the hardware for that virtual memory.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Luís Pedro Coelho]

Luís Pedro Coelho  added the comment:

Original poster here.

The benchmark is artificial, but the problem setting is not. I did have a 
problem that is roughly:

interesting = set(line.strip() for line in open(...))
for line in open(...):
key,rest = line.split('\t', 1)
if key in interesting:
 process(rest)

Deleting the set (when it goes out of scope) was a significant chunk of the 
time. Surprisingly, deleting a very large set takes much longer than creating 
it.

Here are my controlled measurements (created with the attached script, which 
itself uses Jug http://jug.rtfd.io and assumes a file `input.txt` is present).


Ncreate (s) delete (s)
   1 0.00 0.00
  10 0.00 0.00
 100 0.00 0.00
1000 0.00 0.00
   1 0.01 0.00
  10 0.15 0.01
 100 1.14 0.12
100011.44 2.24
   1   126.4170.34
   2   198.04   258.44
   3   341.27   646.81
   4   522.70  1044.97
   5   564.07  1744.54
   6  1380.04  3364.06
   7  1797.82  3300.20
   8  1294.20  4410.22
   9  3045.38  7646.59
  10  3467.31 11042.97
  11  5162.35 13750.22
  12  6581.90 12544.67
  13  1612.60 17204.67
  14  1788.13 23772.84
  15  6922.16 25068.49

--
nosy: +l...@luispedro.org
Added file: https://bugs.python.org/file47448/time-set.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Random idea:  For some range of array sizes (bigger than L3 cache), there might 
be a net benefit to sorting L1-sized clumps of pointers before making the 
Py_DECREF calls.  Possibly, the cost of sorting would be offset by improved 
memory access patterns.

On the other hand, this might just optimize an artificial benchmark that isn't 
representative of real code where the data is actually being used.  In that 
case, the program is already going to have to hop all over memory just to 
access the referred-to objects.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Raymond Hettinger]

Raymond Hettinger  added the comment:

The 4th graph in this article may be showing the reason for the growth in 
random access times as the size gets bigger:

https://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Raymond Hettinger]

Raymond Hettinger  added the comment:

> In former examples (list, ordered dict) objects are iterated and deleted 
>in order of creation. But in the set of strings items are deleted in
> non-predicable random order. I suppose the non-linear effect is 
> related to memory management.

That makes sense.  We're likely seeing an artifact of a favorable 
correspondence between the container pointer order and the order that the 
referred-to objects were created in memory in this somewhat non-representative 
test case.  That is why lists lose the favorable timing when the data is 
shuffled.

If the test bench creates all the referred-to objects in consecutive memory 
locations, then any container accessing those objects consecutively will 
benefit from spatial cache locality.  (i.e. If there is more than one datum per 
cache line, the second read is virtually free.  Likewise, memory controller 
read-ahead makes a long series of consecutive accesses cheaper.)

It would be nice is the timing were run on strings instead of integers.  Ints 
are somewhat weird in that the hashes of consecutive integers are themselves 
consecutive, you can fit two ints in one cache line. 

I'm not sure whether it applies here, but there may also be a branch-prediction 
effect as well:  
https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array

FWIW, the deallocation routine for sets isn't doing anything special.  It just 
calls Py_DECREF in a loop:

static void
set_dealloc(PySetObject *so)
{
setentry *entry;
Py_ssize_t used = so->used;

/* bpo-31095: UnTrack is needed before calling any callbacks */
PyObject_GC_UnTrack(so);
Py_TRASHCAN_SAFE_BEGIN(so)
if (so->weakreflist != NULL)
PyObject_ClearWeakRefs((PyObject *) so);

for (entry = so->table; used > 0; entry++) {
if (entry->key && entry->key != dummy) {
used--;
Py_DECREF(entry->key);
}
}
if (so->table != so->smalltable)
PyMem_DEL(so->table);
Py_TYPE(so)->tp_free(so);
Py_TRASHCAN_SAFE_END(so)
}

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Serhiy Storchaka]

Change by Serhiy Storchaka :


Added file: https://bugs.python.org/file47447/bench_del.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[INADA Naoki]

Change by INADA Naoki :


--
nosy: +inada.naoki

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

For lists and dicts the time of deletion is virtually linear.

1 int   5.2   9.8
2 int   5.8   9.7
4 int   5.6   9.8
8 int   5.8   10.0
16 int   5.5   9.7
32 int   5.4   9.6
64 int   5.6   9.0
128 int   5.6   8.7
1 str   7.6   13.3
2 str   8.0   13.8
4 str   7.4   14.0
8 str   7.5   14.3
16 str   7.6   14.4
32 str   8.0   14.7
64 str   7.9   14.3
100 str   8.1   14.0

1 int   60.4   10.5
2 int   61.0   11.1
4 int   61.1   10.4
8 int   60.1   11.1
16 int   61.1   10.1
32 int   61.5   9.9
64 int   60.7   9.6
128 int   60.8   9.4
1 str   204.9   15.4
2 str   247.4   15.8
4 str   275.3   16.1
8 str   299.3   14.8
16 str   312.8   14.8
32 str   329.2   14.2
64 str   344.5   14.1
100 str   386.2   14.4

(third and forth columns are time in nanoseconds per item, for creation and 
deletion)

But when shuffle the input data before creating a collection, the deletion time 
becomes superlinear (and much slower).

1 int   17.4   38.9
2 int   19.1   41.3
4 int   24.4   46.3
8 int   28.0   49.5
16 int   28.1   53.4
32 int   29.8   67.2
64 int   35.2   90.6
128 int   42.6   143.1
1 str   21.1   56.3
2 str   24.3   58.2
4 str   27.1   63.6
8 str   27.3   73.9
16 str   29.4   99.2
32 str   34.3   144.8
64 str   41.8   229.5
100 str   46.3   338.4

In former examples (list, ordered dict) objects are iterated and deleted in 
order of creation. But in the set of strings items are deleted in 
non-predicable random order. I suppose the non-linear effect is related to 
memory management.

--
nosy: +lemburg, tim.peters, twouters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32846] Deletion of large sets of strings is extra slow

[Terry J. Reedy]

New submission from Terry J. Reedy :

https://metarabbit.wordpress.com/2018/02/05/pythons-weak-performance-matters/, 
a blog post on cpython speed, clains "deleting a set of 1 billion strings takes 
>12 hours".  (No other details provided.)

I don't have the 100+ gigabytes of ram needed to confirm this, but with 
installed 64 bit 3.7.0b1 with Win10 and 12 gigabyes, I confirmed that there is 
a pronounced super-linear growth in string set deletion (unlike with an integer 
set).  At least half of ram was available.

  Seconds to create and delete sets
millionsintegersstrings
of items  create delete  create delete
   1 .08.02 .36.08
   2 .15.03 .75.17
   4 .30.061.55.36
   8 .61.123.18.76
  161.22.246.48   1.80  < slightly more than double
  322.4 .50   13.65.56  < more than triple
  644.91.04   28 19 < nearly quadruple
 128   10.92.25
 100  56 80 < quadruple with 1.5 x size

For 100 million strings, I got about the same 56 and 80 seconds when timing 
with a clock, without the timeit gc suppression.  I interrupted the 128M string 
run after several minutes.  Even if there is swapping to disk during creation, 
I would not expect it during deletion.

The timeit code:

import timeit

for i in (1,2,4,8,16,32,64,128):
print(i, 'int')
print(timeit.Timer(f's = {{n for n in range({i}*100)}}')
  .timeit(number=1))
print(timeit.Timer('del s', f's = {{n for n in range({i}*100)}}')
  .timeit(number=1))

for i in (1,2,4,8,16,32,64,100):
print(i, 'str')
print(timeit.Timer(f's = {{str(n) for n in range({i}*100)}}')
  .timeit(number=1))
print(timeit.Timer('del s', f's = {{str(n) for n in range({i}*100)}}')
  .timeit(number=1))

Raymond, I believe you monitor the set implementation, and I know Victor is 
interested in timing and performance.

--
messages: 312188
nosy: rhettinger, terry.reedy, vstinner
priority: normal
severity: normal
stage: needs patch
status: open
title: Deletion of large sets of strings is extra slow
type: performance
versions: Python 3.7, Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com