On Thu, Sep 19, 2019 at 10:32 PM Steven D'Aprano <steve@pearwood.info> wrote:

On Thu, Sep 19, 2019 at 03:26:27PM +1000, Chris Angelico wrote:

...

On Thu, Sep 19, 2019 at 3:08 PM Richard Higginbotham <higginbr@gmail.com> wrote:

...

I'm not sure if there is any interest by others but I have frequently come across cases where I would like to compare items in one list in another similar to relational algebra. For example are the file names in A in B and if so return a new list with those items. Long story short, I wrote some functions to do that. They are quite simple and fast (due to timsort in no small part). Even the plain python code is faster than the built in set functions (afaik). I created a github and put the ones I thought the community might like in there. https://github.com/ponderpanda/listex

an example would be a = [1,2,3,4,5,6] b = [1,3,7,4] list_intersection(a,b, sorta=True, sortb=True)

returns [1,3,4]

Can you elaborate on how this differs from using the built-in set type for set operations? eg is this for situations where the values are not all hashable?

Sets are unordered and can contain no duplicates. Lists are ordered and can contain duplicates, so you might think of them as "ordered multisets".

With the sorta/sortb API and the algorithmic assumption that the heads of both lists can be checked, I think the value of element order has been lost, so the only significance is the possibility of duplicates. The given use-case of file names doesn't justify this. So I'm curious what the OP's actual use-case was for using lists here. ChrisA

On Fri, Sep 20, 2019 at 5:11 AM Richard Higginbotham <higginbr@gmail.com> wrote:

The original use case was detecting new files in various directories. Each directory was expected to have millions of 4KB files and maybe at most 100k of new files. This was in around 2002 and it was a huge time savings for me.

I can't help thinking that the time for such a job would be dominated by disk operations here :) If a single directory has quote "millions" of files, you're going to see some pretty significant differences based on which file system you're using; not every FS copes well with gigantic directories. ChrisA

On Fri, Sep 20, 2019 at 6:31 AM Richard Higginbotham <higginbr@gmail.com> wrote:

That's exactly what I expected. It's the opposite though. The time to check one list for all the elements in another list was far longer. Granted this was a Linux box using ext2. The other helpful element is that the filesystem returned the files in the proper order. One of the tests runs I mentioned was A 100000, B 500000 because that was a realistic scenario. If you actually try that with the naive method you will be waiting for a very long time to get a result, even today. Using sets, if you know to use sets, then its only a 10th of a second. I think both those methods are polynomical run time so I was pretty proud of my linear solution at the time.

Please quote some text to give context. WHAT is exactly what you expected? Building a set out of a series of values takes linear time, and set intersection also takes linear time. On what basis do you say that "both these methods" (again, not sure what you're referencing since you didn't quote any text) have polynomial run time? ChrisA

On Sep 19, 2019, at 12:09, Richard Higginbotham <higginbr@gmail.com> wrote:

It might / probably? even be adapted to be used in the built in set operations.

How? I’m not sure if you get how sets work, and maybe you think they’re based on a red-black tree or skiplist or some other logarithmic collection, like C++ and Java sets? It that were true, then implementing set.intersection as a step-compare instead of just {x for x in self if x in y} would be an optimization—it would replace O(nlogm) time with O(n+m). (But then such a set would almost certainly already be using step-comparison—or, in fact, would already be optimized it with subtree pruning, which has the same worst case but better best case—before anyone added it as a builtin.) But sets actually use a hash table, just like dicts do. This means they work on objects that can’t be compared (e.g., you can throw a bunch of complex numbers in a set). So you couldn’t possibly use an algorithm that requires comparison to implement a set method, because it would raise a TypeError on perfectly valid sets. This also means that lookup is an O(1) operation, not O(logn). So, intersection is O(m) time, which is better than your O(n+m), not worse. It also means that insert is amortized O(1) time, so you can build a set in O(n) time. So, if the collections aren’t prepared in advance, building a set to intersect with an iterable is O(n+m) time, which is better than sorting two iterables to step-compare them in O(nlogn+mlogm+n+m) as you’re proposing.

On Fri, Sep 20, 2019 at 5:08 AM Richard Higginbotham <higginbr@gmail.com> wrote:

Its faster than the built in set type. Uniqueness of values isn't a requirement. The values need to be comparable so that they can be sorted. This allows a linear time complexity.

Note that the linear time complexity assumes that they have *already* been sorted (not just that they *can be* sorted), as otherwise the process will incur an O(n log n) sort step first. ChrisA

On Sep 19, 2019, at 12:07, Richard Higginbotham <higginbr@gmail.com> wrote:

Its faster than the built in set type.

Not according to timeit. If you want to dispute that, you need a proper benchmark, not just repeating the claims from your inaccurate one. I’m not sure what your relationtype is supposed to do (especially given than 1 and 2 produce the same values), and all versions seem like unusual use cases rather than anything approaching realistic, but I left that all alone and just replaced your benchmarks with timeit, repeated them enough times to actually be meaningful, and changed the test to the operation you claim it’s about rather than a different one. The output pretty clearly shows that a pre-existing set beats a pre-sorted list, and building a set on the fly beats sorting a list on the fly, and even comparing blatantly unfairly with building a set on the fly vs. using a pre-sorted list, the set still wins except in the smallest test. I didn’t include tests against more realistic datasets where your algorithm does significantly worse; this shows that even your chosen input is slower with your algorithm if you measure it properly. And, while we’re at it, I added a version of your algorithm that works with arbitrary iterables and also takes a key function (which you always want when you’re doing anything related to sorting in Python), and it’s about 10-20% faster than your list version, which shows that you aren’t getting any performance benefit from restricting yourself to lists only. See https://pastebin.com/BC2zgtN6 for the code.

Uniqueness of values isn't a requirement.

Of course. But non-unique values make the set algorithm faster, and they make your algorithm slower. And nearly-unique values don’t affect the set time, but they make your algorithm slower. So you can’t just ignore it. And, again, you have to decide what happens with non-unique values, how many times they appear in the output.

The values need to be comparable so that they can be sorted. This allows a linear time complexity.

Except that sorting is log-linear, not linear, so it doesn’t. Meanwhile, set actually _does_ allow linear time complexity. Again, none of this means your code is useless. I think a step-compare intersection is useful enough to belong in itertools, at least as a recipe. But it’s not faster than set, or simpler, or anything else you’re arguing.

...

For example are the file names in A in B and if so return a new list with those items. Long story short, I wrote some functions to do that. They are quite simple and fast (due to timsort in no small part). Even the plain python code is faster than the built in set functions (afaik). You’re testing pretty small values in a very narrow use case, and testing them inaccurately by using datetime instead of timeit (the fact that some of your results are 0 vs. 0 should be a clue…), and you haven’t even given us the results, just claimed that they’re faster.

When I run my own test on lists of 10000 strings made up 5 random lowercase characters, I get 485us for set(a).intersection(b), and 6609us for list_intersection(a, b), so it’s actually more than 10x slower. I can't reproduce this here is what I get For A not in B:

I'm sorry I haven't used the mail list before and didn't send my comments to the list. Please see my response to Chris for some example times. I'm reluctant to use anything less than about a ms for timing purposes. There's too many interactions at the us level that can skew results. I'd prefer to expand the sample size until it's more clear. Here is an example For A not in B: trying A 10000, B 50000 naive test 0:00:10.319032 set test 0:00:00.009001 listex test 0:00:00.005000 For A subset of B: trying A 100000, B 500000 set test 0:00:00.180018 listex test 0:00:00.054006 If I increase a and b by 10 times the execution time goes up by about 100x on the set. This is because its related to a * b. the listex only goes up by about 10x which is about 10a + 10b. trying A 10000, B 10000 naive test 0:00:02.661266 set test 0:00:00.002000 listex test 0:00:00.005001

...

The complexity ends up being about the longer of list a or b. How can that be true? Sorting a takes nlogn steps, sorting b takes mlogm steps, step-comparing then takes n+m steps, so that’s O(nlogn + mlogm * n + m) = O(nlogn), which i>s bigger than O(n). I should have been more specific. The readme.md in the project explains a little more as does my response to Chris. You are right the sort + alg operation takes n log n and m log m just to sort the lists. The intersection,union, other functions though are m + n. The total is O(m+n+nlogn+mlogm). There is no multiplication of the sort time and the relation operation time because you only have to do it once no matter how many items are in a or b.

Why would you want this as a method of list rather than a function that works just as well on any sortable iterables? It doesn't have to be. I just thought that was the purpose of this list so I should start with that. A stand alone module works for me at the moment. If it were included in the list functions or as some "extra" function that worked on lists I figured the final result would be done in C like the sort() function. That would make it a significant change so my idea was just to present the algorithms and see if there was interest. If it is in a addon package that would be ok with me, but I think think people would use the set method and probably never know there was a better way.

c = [val for val in a if val in filterset] This is the crux I think. The complexity is the number of elements in filterset. Since filterset has to be check for every value in a its O(len(a) * len(b) * filter search time). You wrote O(n+m) but I think that is incorrect.

The module (listex) I linked to implements the other operations as well. I didn't mean just intersection I was just using that as an example. If you run the module it will generate some time comparison for that, but its just for comparison not meant to be exhaustive. It's the set of functions I have found useful in the past. It's not all of the ones in the module I regularly use for purely academic purposes actually.

It's not really constant though. Look at all of the test results here. Richard Musil in the following post shows one value of A=1000,B=10000 with .034 ms and the next point A=10000,B=50000 If the hash were constant time and A increased by 10x then the time should be 0.34ms but its not. It's 0.54 ms. The next step up is 8.5ms instead of 0.54 ms. If you start including the time it takes to convert lists to sets its even more pronounced. hash values can collide and the bigger the data set the more likely it is to happen. Perfect hash functions don't exist.

You know, if anyone wanted a good example of why Computer Science courses should carry on teaching about sorting algorithms despite them being already implemented for you these days, this thread is it. Very nicely explained, folks! -- Rhodri James *-* Kynesim Ltd

[Richard Higginbotham <higginbr@gmail.com>]

If you start including the time it takes to convert lists to sets its even more pronounced. hash values can collide and the bigger the data set the more likely it is to happen.

That's not so. Python's hash tables dynamically resize so that the load factor never exceeds 2/3. The worst case then is a "large" table as full as it's allowed to get before Python grows its size. In that case, the average number of probes for a successful search is 1.65, and for a failing search 3.00. It doesn't matter to this how large the tables get. For very small tables, the average values are lower, but 1.65/3.00 is good to the full 3 digits already at tables with 4096 slots (which can hold at most 2730 items). Of course there are pathological cases, but they're exceedingly unlikely to occur when using strings as keys, because Python's string hashes are a good approximation to (pseudo)random.

Perfect hash functions don't exist.

Of course they do, but it's impractically expensive to construct a perfect hash function for dynamically changing data. In Python, it so happens that when dict keys (or sets) consist of a contiguous range of integers (range(J. J+N) for some J and N), the integer hash function usually IS "perfect": no collisions at all. That's intentional and unusual, and follows in part from that hash(J) == J for "not huge" positive integers J. Something I haven't seen mentioned here, but I may have missed it: when timing algorithms with sets and dicts, people often end up merely measuring the bad effects of hardware data cache misses when the containers get large, and especially in contrived benchmarks. In those the base data tends to get built up in a contiguous range of memory, and storing the objects in a list leaves traversing the list fetching the objects' data in the same contiguous memory order. It's as cache-friendly as can be. Traversing via a set or dict instead reads the objects' data in pseudo-random memory order instead, which can give a very high rate of cache misses. In addition, the internal hash table probes also occur in pseudo-random order, adding yet another layer of cache misses. Plain old lists are in fact pleasant in many ways :-)

On Thu, Sep 19, 2019 at 10:25:20PM -0500, Tim Peters wrote: [...]

...

Something I haven't seen mentioned here, but I may have missed it: when timing algorithms with sets and dicts, people often end up merely measuring the bad effects of hardware data cache misses when the containers get large, and especially in contrived benchmarks.

In those the base data tends to get built up in a contiguous range of memory, and storing the objects in a list leaves traversing the list fetching the objects' data in the same contiguous memory order. It's as cache-friendly as can be.

This is an interesting point, which is difficult to deduce without an implementation insight. I would for example assume that there is a "list construct" which holds just the references to the actual objects (strings in our example here) and the same for the dict (hashmap), so the actual objects could be anywhere, while the "list" or "dict" can be in one (memory) place. Did you mean that, or that also the object themselves are in the "same place"? I believe there are two factors which may affect the performance. The cache miss on actual data objects (e.g. the strings), and the cache miss on the "construct" object (i.e. the list or dict). But I have no idea how big are lists or dicts (of the same size), or even if all those assumptions above are correct. On Fri, Sep 20, 2019 at 10:43 AM Steven D'Aprano <steve@pearwood.info> wrote:

I'm not sure if this is something specific to timing tests, or if it will hold for real-world data in non-contrived code too.

The only thing which could impact it on the "real data" is an execution environment, i.e. for example, if the cores/threads are loaded and the operations get preemtped by the scheduler (which would also invalidate the cache). Then depending on the frequency of those invalidation it could make the importance of the "fit into cache" condition less important. But it would depend on the system scheduler and the platform configuration (may differ on the server and on the normal desktop machine). But technically the difference should not be bigger on the real data. Richard

[Tim]

...

Something I haven't seen mentioned here, but I may have missed it: when timing algorithms with sets and dicts, people often end up merely measuring the bad effects of hardware data cache misses when the containers get large, and especially in contrived benchmarks.

In those the base data tends to get built up in a contiguous range of memory, and storing the objects in a list leaves traversing the list fetching the objects' data in the same contiguous memory order. It's as cache-friendly as can be.

[Steven D'Aprano <steve@pearwood.info>]

I'm not sure if this is something specific to timing tests, or if it will hold for real-world data in non-contrived code too.

Depends on the data access patterns of the app. There's really no simple way to know. One possible clue: in recent CPythons, sys._debugmallocstats() can be called to get info about the state of Python's small object allocator. Compare the "# bytes in allocated blocks" output line to the total number of bytes across all arenas. If that ratio is close to 1.0 then at least we're _using_ most of arena memory. The closer to 0 it gets, the more data is splattered around, with large gaps between used bytes. Since CPython _never_ moves an object in memory, fragmentation can become nearly arbitrarily bad. As bad as using only 8 bytes out of each 256 KiB allocated (although I expect it would take effort to contrive a program in the same universe as being that bad).

If it holds for real data, then presumably it counts as as advantage of lists over sets. But if it is an artifact of naive/contrived timing tests, is there something we can do to make the tests less naive?

What's the first rule of benchmarking? RUN ON A MACHINE AS QUIET AS POSSIBLE So it's deliberately and spectacularly naive. Benchmark results should really be viewed as lower bounds: guarantees that no related real-life code will ever run faster, and almost always slower ;-) They remain the easiest way to guess whether one approach "is likely to" run faster than another, though. An easy example of major cache effects: xs = list(range(1000000)) sum(xs) Then do the same, but use random.shuffle(xs) before summing. Just timing the `sum(xs)` part, a quick timeit run on my non-quiet box just now showed the latter taking well over 4x longer. The original spelling tends to access RAM (for the guts of the int objects) in sequential order, but shuffle first and sum() leaps all over RAM to get from one int to the next. The memory layout is the same either way, so staring at obmalloc stats won't yield any clue in that case.

On Sep 19, 2019, at 20:25, Tim Peters <tim.peters@gmail.com> wrote:

Something I haven't seen mentioned here, but I may have missed it: when timing algorithms with sets and dicts, people often end up merely measuring the bad effects of hardware data cache misses when the containers get large, and especially in contrived benchmarks.

Another issue: the container itself is larger. A list’s array uses one pointer (8 bytes) per element. Even without looking at the implementation of set, a hash bucket obviously has to be at least twice that size. Plus, lists need less slack, and put their slack all at the end where you don’t need to traverse, while hash tables have their slack distributed within the table where it does get in the way. So, a list should be able to go at least 2.2x as big as a set before hitting the threshold where it’s no longer all in cache. But of course this is only true if you can forget about the objects themselves. Each string object is a lot more than 16 bytes, and the character strings themselves are as well in most tests, so the top-level difference is often swamped. Still, the nonlinear jumps when you cross boundaries like “everything in cache”, “at least the top level all in cache”, etc. (and at each level of cache) might be visible distortions (or visible reflections of a real benefit, if your application’s behavior is close enough to the artificial benchmark). You can test the behavior of list here by using a huge list of numbers from 1 to 100… but you can’t do that with set, because that would be a tiny set of 100 elements. And of course even once you know the exact characteristics of the cache behavior with your real data, that can be hard to optimize for beyond “try to keep adjacent things adjacent”. There’s a paper from the GHC guys many years ago about how they cleverly tuned the ropes (linked lists of mid-sized arrays) they used to optimize large string internals around the L2 cache and found that the code that worked great on their older Intel CPU was a huge pessimization on the next generation of CPUs because they were fooling the computer into thinking they were never going to read past the end of the current page so it didn’t prefetch the next one.

On Thu, Sep 19, 2019 at 11:58 PM Richard Musil <risa2000x@gmail.com> wrote:

I did not verify the results (I hope they are correct), but the timing suggest that the set operation is always faster. When however we add the set setup to the mix, the build up time, which is O(n + m) becomes more significant than actually sorting and comparing the lists which is technically of O(nlog(n) + mlog(m)). It would also suggest that for some large lists the list implementation _can_ actually be faster if we calculate in an eventual conversion of the lists to the sets and possible even more faster if the lists were already ordered.

Ok, I misread the original code, the lists were not sorted in the previous results (and their should be). So with the correction to have them sorted, the results are: For A not in B: trying A 1000, B 5000 best naive_relcomp test time (msec): 38.147 best relcomp_set test time (msec): 0.035 best relcomp_set with set init test time (msec): 0.219 best list_relcomp test time (msec): 0.330 For A not in B: trying A 10000, B 50000 best relcomp_set test time (msec): 0.546 best relcomp_set with set init test time (msec): 3.293 best list_relcomp test time (msec): 3.493 For A subset of B: trying A 100000, B 500000 best relcomp_set test time (msec): 8.651 best relcomp_set with set init test time (msec): 55.133 best list_relcomp test time (msec): 144.094 Which actually puts it in line with the expectations. I guess there is not much more to say. Richard M.

On Fri, Sep 20, 2019 at 1:52 AM Andrew Barnert <abarnert@yahoo.com> wrote:

On Sep 19, 2019, at 15:18, Richard Musil <risa2000x@gmail.com> wrote:

...

Ok, I misread the original code, the lists were not sorted in the

previous results (and their should be). So with the correction to have them sorted,

I think to be fair, you want to show it _both_ ways, just as you’re showing sets both with and without creating the sets. Because sometimes you’re already going to have sorted lists, just as sometimes you’re already going to have sets.

Right. It just was giving wrong results and I was not sure if the algorithm on "particularly unsorted" list would be representative (because it would produce the wrong results), so I removed it. I added a new test `list_relcomp[presorted]` with pre-sorted (just to have the results correct) to see if "making it correct" has any impact. So there are four things to compare:

* set operation on existing sets * set operation including time to build the sets * step-compare operation on pre-sorted lists * step-compare including time to sort the lists

(Also, for the set operation, there’s no need to build _two_ sets. Just build a set of one and intersect it with the other list.)

Right (again). When I was considering the algorithm on the lists, I thought that technically, I could build just one set on the fly, but the other one has to be at least hashed to test the inclusion, and I also assumed that the hash operation will be dominant in this and basically told myself that the cost of building the other set will not be significant. I just added another implementation to the test (which I believe you had on mind): ``` def relcomp_set_list(a, b): bset = set(b) return [ia for ia in a if ia not in bset] ``` and confirmed that avoiding the 2nd set build actually brings a noticeable improvement :). I also changed the naming as the original code used `relcomp_set` to mark set operation 'a - b', but returned the results as the list, which seemed to me a bit confusing, so I renamed it to `relcomp_set_to_list` (do not confuse it with `relcomp_set_list` mentioned above) and put there `relcomp_set`, which does pure set 'a - b' and returns a set. So one can see the overhead of the resulting list construction in the original `relcomp_set`. The results are: For A not in B: trying A 1000, B 5000 naive_relcomp (msec): 38.105 relcomp_set (msec): 0.025 relcomp_set_to_list (msec): 0.034 relcomp_set with set init (msec): 0.215 relcomp_set_list (msec): 0.192 list_relcomp (msec): 0.329 list_relcomp[presorted] (msec): 0.214 For A not in B: trying A 10000, B 50000 relcomp_set (msec): 0.416 relcomp_set_to_list (msec): 0.545 relcomp_set with set init (msec): 3.167 relcomp_set_list (msec): 2.546 list_relcomp (msec): 3.372 list_relcomp[presorted] (msec): 2.005 For A subset of B: trying A 100000, B 500000 relcomp_set (msec): 8.557 relcomp_set_to_list (msec): 8.519 relcomp_set with set init (msec): 55.783 relcomp_set_list (msec): 48.903 list_relcomp (msec): 143.577 list_relcomp[presorted] (msec): 120.911 There is still one peculiarity in the last test, where relcomp_set and relcomp_set_to_list gave basically the same result. I interpret is as that the result is of a small size, basically insignificant to the other operations in play. Richard M.

Richard Musil wrote:

On Fri, Sep 20, 2019 at 1:52 AM Andrew Barnert abarnert@yahoo.com wrote:

...

On Sep 19, 2019, at 15:18, Richard Musil risa2000x@gmail.com wrote:

After some thought I don't think the the time comparisons are useful unless we include the set init time. If we already have two sets, would anyone want to compare and convert that into a list? In the use case where we read a list of files, wouldn't we want to put that into a list instead of a set? I would think we would only put it into a list if we knew we would be doing set operations. At that point we would need to compare adding the elements individually to a list versus a set to then compare the set operations with list operations fairly. At small data sizes we are probably just comparing the speed of python with C. Perhaps I should write a C extension module to make sure its and apples to apples comparison. I'll try that when I get some time.

BTW, this thread seems a good place to mention the under-appreciated SortedContainers package from Grant Jenks: http://www.grantjenks.com/docs/sortedcontainers/ This supplies sorted containers (lists, dicts, sets) coded in pure Python, which generally run at least as fast as C extensions implementing fancy tree structures. The basic implementation "trick" is to maintain, under the covers, a list _of_ Python lists. Not deeper than that. It you're familiar with the lingo, it's most like a memory-resident 2-level B-tree. It scales extremely well, to billions of elements - to sizes the fancy packages can't get near, because their space overheads are so much higher they run out of RAM. There's extensive explanation of that here, which should be read to get a feel for just how much of modern processor behavior hasn't even been mentioned in _this_ thread ;-) http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html Here's a tease: """ For comparison, consider traversing an AVL-binary tree with one billion elements. A highly optimized implementation will require at least 24 gigabytes of memory. The binary tree will likely traverse thirty levels, each of which is a data-dependent lookup. Some lookups will have good locality but most will not. Each lookup could be hundreds to thousands of times slower than sequential accesses. These slow lookups are why Sorted Containers can afford to shift a thousand sequential elements in memory and have most additions take less time than binary tree implementations. """ It was very much designed with cache behavior in mind, where a hit in L1 cache can easily be 100 times faster than needing to go to RAM. That said, the package's SortedSet still uses a Python set under the covers, because he didn't find anything that could beat that. The sorted order is maintained, under the covers, in a parallel SortedList. For that reason, adding an element to (or removing one from) a SortedSet takes O(log(N)) time rather than O(1).

On Sat, Sep 21, 2019 at 7:54 AM Richard Higginbotham <higginbr@gmail.com> wrote:

I'm not concerned about micro op, I'm concerned with macro op on large data sets. Right now if someone comes to you with that simple use case of two large lists you have to tell them to convert to sets and then back again. Forget the new programmers who tried the naive way and quite because "python is too slow", they are waiting 20 seconds when we could deliver it to them in 1 second. If I can get within 10x of C code that seems like it would be useful for that type of use case. I don't know if my case is common and I've used it on more esoteric problems that wouldn't expect anyone to do, I'm used to dealing with a lot of data, but if it can be of help I came it to make it available.

If you directly construct a set from your source of truth (eg from a directory iterator, if you're looking at file names), you don't have to "convert a list to a set". Even if you did have to convert (or technically, to construct a set with the elements of that list), how many elements do you need before it's actually going to take an appreciable amount of time? I don't mean a measurable amount of time - a handful of microseconds can be measured easily - but a length of time that would actually make people consider your program slow, which probably means half a second. Now multiply that number of elements by, say, 64 bytes apiece (15-character strings in Python 3.4+), and see if that would mean you have other issues than the actual hashing. I think you're still looking at a microoptimization here. ChrisA

Andrew Barnert wrote:

On Sep 20, 2019, at 14:51, Richard Higginbotham higginbr@gmail.com wrote:

...

Andrew Barnert wrote: What’s the goal here? I'm not concerned about micro op, I'm concerned with macro op on large data sets. Right now if someone comes to you with that simple use case of two large lists you have to tell them to convert to sets and then back again. Forget the new programmers who tried the naive way and quite because "python is too slow", they are waiting 20 seconds when we could deliver it to them in 1 second. But today, you can deliver it to them in 1 second: just give them set(b).intersection(a) or set(a) & set(b) or sb = set(b) then [x for x in a if x in sb] and you’re done. They can easily understand why it works. If they want to know why it’s faster, you can easily explain it, and they’ve learned something widely useful.

This isn't technically correct. It's not faster. It all depends on the use case which when it contradicts your expectations you just deride as "artifical micro benchmarks". Python isn't just used as a toy scripting language. 50 million elements in a collection is not even large by a long shot at least from where I sit. You can make a case that it's not a good language for that type of problem, say HPC clusters. Or you can tell people to go copy some C code "like people have been doing for decades". That you ask if that is a proper response to your users is very concerning to me.

If we add a new function, whether it’s in builtins or itertools or elsewhere, then you can give them that function and you’re done; that’s no easier or harder. They probably won’t immediately know how it works, but if they ask, they’ll learn something useful. And once they get why it works, they probably will get why it’s faster. So, overall, the new solution is roughly the same benefits as the existing one that’s been there since Python 2.3.

...

I think it’s pretty easy to establish that sets are fast but they’re not magic, sorting is pretty good but it’s not magic, there are some cases where step-compare is faster if you have already-sorted lists… and none of this matters anyway, because in real life there are very few use cases where you can equally choose between sets and step compare and need to micro-optimize, but lots of cases where you have _other_ reasons to choose between them. There is no step compare option in python now though. You either convert to set or you hope the sun doesn't expire before your program finishes. Or you write the step-compare manually, the way C programmers have done for decades. Or you find a third-party library or copy and paste code off a Stack Overflow answer. Converting to set is easier, and usually the right answer. The important question is, for those cases where it _isn’t_ the right answer, is “write it yourself or find it on SO” good enough?

So now all the scientist using Python also need to learn C, or at least be quick to copy, paste, or know the "secret" knowledge of using sets except for their problems it may be much slower.. so they'll also need to know all about pythons implementations of sets, cache misses, and those artificial micro benchmarks that give people a sad so we can't talk about. I'm actually OK with that as an answer as condescending and unprofessional as it may be.

...

Sets work on non-comparable values; step-compare works on non-hashable values. Step-compare (if implemented right) works on lazy iterables; sets can preserve the order of the “master”input. They do different things with duplicates. Even when performance is the only issue (and it’s not dominated by the file system anyway, as it would be in your case), the characteristics of your specific data are going to make a huge difference. Not to mention that there are often other compelling reasons to have a set or a sorted list, at which point the choice is made for you. So, this already eliminates the possibility of reimplementing set operations with step-compare as suggested earlier. But it also already makes a compelling case for adding step-compare functions to Python—but that case needs to be made clearly. I'm trying to make that case. No you’re not. You’re trying to make the case that step-compare is better than set in all uses. Which isn’t true. And it isn’t necessary in the first place.

If you ever find yourself arguing that you know what someone else is thinking better than they do, you should stop right there because you are probably wrong.

The case that needs to be made is that it’s good for some cases that we can’t handle today, and that at least one of those cases matters, and that the current state of affairs where people have to go figure out how to do it is not good enough.

So someone can drop by in an attempt to help you so long as they come on hand and knee and prove to you that you need their help. I don't think that can ever work. When you start off by saying their use case doesn't matter it's clear you've already made up your mind. It's obvious you've taken this personally and would go through any hurdle to thwart a consideration of my proposal. That's OK, like I said it wasn't for me, it was for other people.

...

I've never come across another step and compare. People do this all over the place. For example look at the merge step of any merge sort: it’s a step-compare union, possibly in-place, possibly n-ary instead of binary, but recognizably the same thing.

I thought we were talking about Python and algebraic set operations and I said after my previous work I never needed to..

In C++, the stdlib has all of these algorithms, abstracted to work on any forward Iterators, in two versions that handle duplicates differently, plus in-place versions of some of them.

I did exactly what you just said earlier I wrote a C extension for this. I suspect I could do it again, but as it would be an investment of time and effort so I thought I would try to get a consensus view. This process and in particular this discussion has convinced me that even if I want to go out of my way to help this is not the community to be doing it in. There are some good people here who are also very technical. You should talk to them because there is such a huge difference between say the response of Tim Peters and yourself that it's like night and day. That's all I have to say.

Kyle Lahnakoski wrote:

...

Andrew Barnert wrote: set(b).intersection(a) or set(a) & set(b) or sb = set(b) then [x for x in a if x in sb] and you’re done. They can easily understand why it works. If they want to know why it’s faster, you can easily explain it, and they’ve learned something widely useful. This isn't technically correct. It's not faster. It all depends on the use case which when it contradicts your expectations you just deride as "artifical micro benchmarks". Python isn't just used as a toy scripting language. 50 million elements in a collection is not even large by a long shot at least from where I sit. You can make a case that it's not a good language for that type of problem, say HPC clusters. Or you can tell people to go copy some C code "like people have been doing for decades". That you ask if that is a proper response to your users is very concerning to me. Richard, I can identify with the need to intersect large sets; and I often faced with poor choices when it comes to dealing with them.  I love Python, and I would love to use it for my data munging, but the data is too big to fit in memory and Python is too slow.  I find it disappointing to convert an elegant expression declaring what I want, like "a-b", into code that declares how to do it, like "set(b).intersection(a)".  This disappointment is magnified by the fact someone, somewhere already written code to do set subtraction faster, and I can not use it; my choices are quick ugly code, or a time consuming search for an elegant solution** on the internet. Maybe we are looking for a different type of solution.  You seem to be asking for the elegance of Python with the expression optimization (aka query planning) of a database.  A database may be able to deliver the speeds you require; it can pack data tighter; it has access to more

On 2019-09-20 9:52 p.m., Richard Higginbotham wrote: processors; it may already leverage SIMD; it can optimize the operation according to how big the data is.  I am suggesting a Python container implementation, like sortedcontainers but using a database (maybe Sqlite), may be a solution. Of course, there is the problem of moving data in and out of the database, but maybe that can be amortized over other operations, and made relatively insignificant.  There is the delay when translating __sub_() call into SQL, but maybe that is  relatively small compared to size of work we are requesting. May you link to your repo where these tests are run?  I seem to have lost the link in the long chain of emails on this list.  I am considering adding a Sqlite example, if only to prove to myself that it is the slowest option of all. Thank you. ** The sortedcontainers mentioned is an interesting demonstration of how fast Python can get when you are aware of L1 cache effects.

Hi Kyle, The repo is here: https://github.com/ponderpanda/listex I'm still looking into sortedcontainers and dominik's suggestion of numpy. Both seem promising. At the moment, I'm more concerned with in-memory operations. Disk access complicates things, but I think it would be interesting to include those. We've seen how memory access times can turn superior algorithms into inferior ones at scale. It's very likely that could be true when using disk access times. I'm not sure anyone would want to wait for that benchmark to finish though. My suspicion is that a hybrid approach would be the most optimal. It get's more complicated when you consider you could throw in more computers to increase in memory sizes. If you are going to use my routines for speed testing with large data sets I would try simple timers instead of using the bench mark set. It takes much longer to run the tests repeatedly and the timing precision at scale is going to be drowned out by the long run times. I've been considering parallelization / distribution (sharing cpu and memory) and I think I have a pretty good idea of how to do it. I just haven't needed with my work yet. I think set style (hashtables) would be less likely to benefit from parallelization but I haven't looked into it at all yet. Depending on the size of your datasets you might benefit more from that than relational databases.

On Sep 19, 2019, at 13:18, Richard Higginbotham <higginbr@gmail.com> wrote:

...

...

For example are the file names in A in B and if so return a new list with those items. Long story short, I wrote some functions to do that. They are quite simple and fast (due to timsort in no small part). Even the plain python code is faster than the built in set functions (afaik). You’re testing pretty small values in a very narrow use case, and testing them inaccurately by using datetime instead of timeit (the fact that some of your results are 0 vs. 0 should be a clue…), and you haven’t even given us the results, just claimed that they’re faster.

I'm sorry I haven't used the mail list before and didn't send my comments to the list. Please see my response to Chris for some example times. I'm reluctant to use anything less than about a ms for timing purposes. There's too many interactions at the us level that can skew results.

This is exactly what timeit is for. It repeats the tests multiple times and aggregates appropriately, and it does half a dozen other things that you haven’t even thought of and therefore aren’t even trying to correct for. And of course it’s been tested through decades of widespread use.

Steven D'Aprano wrote:

...

Let me expand on the reasons for my post here. It seems like motivation has turned into a bit of a bike-shead. I don't think that anyone is questioning your motivation. (Although one of your recent replies to Andrew seems to be casting some pretty mean-spirited aspersions on his motivation: "[Andrew] would go through any hurdle to thwart a consideration of my proposal". And honestly, your personal motivation isn't really important. If you are doing it for the fame and money, you'll probably be disappointed. If you are doing it to give back to the Python community, that's great, but

On Fri, Sep 20, 2019 at 11:44:17PM -0000, Richard Higginbotham wrote: the community and the core devs have no obligation to accept it into the standard library. You can always put it on PyPI, you don't need to ask anyone's permission, just go ahead and do it. The core devs have a duty to curate the standard library. They cannot accept everything proposed, regardless of the author's feelings or motivations or how useful it is to them. Also their own personal selfish motivation that they are over-worked and under-appreciated as it is without taking on the burden of yet another library to maintain if it isn't justified. Part of the process for justifying that library or set of algorithms is to run the gauntlet of Python-Ideas, and for good or ill, most of the people here tend to be pretty conservative in technology matters, possibly even more conservative than the core-devs. The people here on Python-Ideas are a subset of the Python community, if you can't convince us that your idea is good, you probably aren't going to get much interest from the rest of the community either. Don't take it personally, it's just the nature of the Python community. If you want a community more open to change, you might consider the Node.js or PHP communities, or so I'm lead to believe. [...]

...

It used to require containers with 100k or more elements to see a speed improvement over some other unnamed methods. These days its closer to 50 million with the only other contender being set (hash based) operations at least that I know of. Am I misunderstanding you? You seem to be saying that your algorithm has become slower. In the past, your algorithm beat other unnamed algorithms for moderate sized lists of 100K elements, but now your algorithm doesn't beat them unless the lists are large, 50 million elements or so. So in relative terms, you seem to be saying that your algorithm is now 500 times slower relative to alternatives than it used to be. I don't think that's what you mean, so can you clarify? Computers have gotten faster over 20 years, especially the ones I can afford. At the same time what was a C extension is now a pure python library. At some point a bubble sort will be just as fast a a merge sort from years ago.

...

I think there is a reasonable chance that if it were

converted to C it would be comparable to if not better than the Set operations for people who wanted lists for what ever reason, even with much smaller data sets. Possibly. As we have seen from this thread, the benefits of locality can sometimes make up for a less sophisticated algorithm. If I've learned anything from this thread, it is that relying on Big Oh to predict performance is even less useful today than it used to be. O( ) from theory is less useful. Looking at the rate of change in data sets is more predictive though.

...

I'm most concerned with getting feedback from the list to determine if it would fit any other use cases. If there is some kind of need for it as a general function. You're on the wrong forum for those questions. Here, we are most concerned with whether or not the proposal is a good fit for the language and stdlib, and the person making the proposal is expected to have done their homework and determined other use-cases first, or at least as part of the process. If you want to maximise the number of people seeing your proposal, which will in turn increase your chances of getting feedback of

[...] potential use-cases, you might try posting it on somewhere like Reddit first. I don't think there are many people who would necessarily benefit now that we have discussed it, it requires large data sets to be differential to other methods. The most useful aspect is probably to show that tailored algorithms are still very beneficial if time consuming, at least for large data sets. That and anyone with serious performance needs should be using C as has always been true.

Richard Musil wrote:

On Sat, Sep 21, 2019 at 1:44 AM Richard Higginbotham higginbr@gmail.com wrote: ..... I wrote all this to show that without an insight it might be sometimes difficult or impossible to do it right (I was caught myself in several pitfalls on my original benchmarks I posted here) and also because it was actually a fun to learn quite a few things from this thread. I am however not convinced that step-compare lists can compete with set operations (even when done on lists) at the current state of things. Richard M. I really appreciate the time and thought you have put into it (and others here as well), and its been educational / fun for me too. One of the concerns I have about using timeit is that it puts a lot of focus on the exact statements that are being executed and all the internals underneath. Looking at "list(set(a).difference(b))"; I suspect what I am seeing is 3 C calls from python. Anything after that is a comparison between C (here) and Python (in list_relcomp). I use Python for prototyping a lot so I tend to look for those situations more.

When I first wrote the algorithms(2000 or so) I compared them to [x for x in a if x in b] and I found that the later was faster. I didn't make sense at first but it was because the 'x in b' is done in C (I had just graduated and started using Python). If the data set was large enough I could see the big O growth was greater for the C version versus the python version. Similar to what we see here in the difference between the set operations and listex. I implemented listex in C and it was much faster at all data sizes over maybe 10 elements. I don't expect the same speedup compared to sets because they are more efficient. I also can't guarantee that the trend of set operations having a higher time growth will hold true for all data sizes. I only point it out and say for some use cases set relation operations aren't optimal, but they may be good enough.

On Sep 22, 2019, at 15:28, Tim Peters <tim.peters@gmail.com> wrote:

That's not by accident - the inspiration for CPython's sort's basic "galloping" approach was taken from this paper, which wasn't about sorting at all:

"Adaptive Set Intersections, Unions, and Differences" (2000) Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro

That's concerned with manipulating large sets represented as sorted sequences. They noticed too that data was "lumpy" in real life, and that paper was the start of a number of papers trying ways to take advantage of that.

So if someone _really_ wants to go gonzo with this, that's a promising approach. Do note, though, that it doesn't fit naturally with iterators. "Galloping" relies on O(1) access to data at arbitrary index positions; it's a fancier variant of binary search

I wonder if you could get any benefit by using something like a skiplist-rope hybrid, where you have effectively O(log n) random access rather than O(1), and can only copy huge chunks with O(log n) large memcopies instead of 1 huge one. Would those costs be enough to sink the benefits of galloping? It wouldn’t be usable in all cases, but there are many cases where your huge input is naturally iterable in this way (a set of files to concatenate, a huge file that you can seek in or mmap chunks of, maybe even a semi-lazy rope that you got from some Rust or Haskell library via ctypes). If you know the size of each iterator, you can build the first level or an approximate skiplist, and build the rest up on the fly to approximate binary search well enough (I think) for the purpose. Anyway, if I really did want to do these operations on massive datasets, I’d look at pandas+HDF5 to see what it can give me before considering implementing anything from scratch. But it could be a fun project… A few further half-formed thoughts on this: For a single huge file treated this way, you’d probably want to look at ripgrep. The author started off with the conventional wisdom on when to read vs. mmap vs. windowed-mmap and quickly discovered that all of the conventional wisdom was so badly out of date as to be useless… Could you get any benefit out of parallelizing the gallop seekaheads? Probably not for 1-10 million, but we are talking about huge datasets here. If you have an Iterator extended with a nextn method that can iterate a large chunk of data at a time (which a file can do if you’re treating it as a sequence of bytes or characters, but if you’re treating it as a sequence of lines it can’t, at least without a second pass…), you could build the same thing—but the cost is that you might easily end up using temporary N/2 memory, which defeats most of the benefits of using arbitrary iterables. C++, Swift, etc. don’t have a notion of a “bisectable Iterator”, where like a bidirectional Iterator it still takes O(m) time to jump forward or backward m steps, but it only takes O(1) time to jump (approximately?) halfway between two known positions. You could easily build that on top of anything random-access, and also on top of anything logarithmic like a tree or skiplist, and it seems like there are useful things you can do with it. Or maybe almost all such things are worth specifializing differently for random-access vs. inherently-logarithmic data structures, or maybe it’s just too hard to come up with a proper useful abstraction?

Tim Peters wrote:

That's not by accident - the inspiration for CPython's sort's basic "galloping" approach was taken from this paper, which wasn't about sorting at all: "Adaptive Set Intersections, Unions, and Differences" (2000) Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro

That's concerned with manipulating large sets represented as sorted sequences. They noticed too that data was "lumpy" in real life, and that paper was the start of a number of papers trying ways to take advantage of that. So if someone _really_ wants to go gonzo with this, that's a promising approach. Do note, though, that it doesn't fit naturally with iterators. "Galloping" relies on O(1) access to data at arbitrary index positions; it's a fancier variant of binary search (see listsort.txt in your CPython source distribution for details). If cache misses can be so expensive, how can that win? Because the number of index accesses per galloping step is logarithmic in the number of sequence elements consumed, and "compare" steps can (very roughly speaking) be skipped entirely for all the sequence elements _not_ touched by the galloping indices.

That's funny as that was about the same time as I was working on my list compare. I actually used a binary search as well. I divided the 'merged' list into three sections a head, body, and tail. The head is where the values in one list are totally outside the other list on the 'low' (in sort order) side. The body was where the two lists started to overlap and I used the minimum of the two lists and a binary search to find that. The tail was the opposite end so there was no need to use a binary search to find where it started (its where one list ends). I was very surprised I could sort the list and step through it with any speed improvement. No matter how I changed the initial list state it was very fast. I expected faster on the upper end with large lists, but not on the lower. My first time using sort and my second python program and I lucked out. Good times!

Richard Musil wrote:

...

I really appreciate the time and thought you have put into it (and others here as well), and its been educational / fun for me too. One of the concerns I have about using timeit is that it puts a lot of focus on the exact statements that are being executed and all the internals underneath. Looking at "list(set(a).difference(b))"; I suspect what I am seeing is 3 C calls from python. Anything after that is a comparison between C (here) and Python (in list_relcomp). I use Python for prototyping a lot so I tend to look for those situations more. I believe that your "suspicion" is correct and the set variant is executed mostly in C code (though I do not have any intimate knowledge of the Python implementation, so I my be wrong), while your code is executed in bytecode and I also believe no one here claimed otherwise. This however is not a

On Mon, Sep 23, 2019 at 12:21 AM Richard Higginbotham higginbr@gmail.com wrote: problem of timeit, which main feature is that it is designed for benchmarking and available in the standard library. So anyone can use it, I see what you are saying, but the reason I put a python function in there that then called the set functions was so that the results wouldn't be so heavily skewed in one direction or the other. I also used the simplest hashable values I could think of (short strings and integers). Testing the run time divergence of algorithms is probably art more than science, but the main point is that if there is a divergence either from one algorithm compared with another or from an algorithm and the theoretical big O, there is a good chance it is significant. The actuall execution times themselves matter less than how they change with increasing data sizes. Outside that, benchmarks don't really matter that much. There's a lot of emphasis on finding the minimal bench mark time but it really doesn't matter. I think the discussion we have had shows that. You can benchmark the wrong thing, or benchmark with the wrong equipment just like you can incorrectly benchmark with theory in substitute of well benchmarking. I think a good argument could be made for using the worst benchmark over the best, or perhaps the worst on the equipment where such an algorithm will actually run. That is probably more true for dealing with large data sets than Python in general, I'm reasonable enough to see that.. You can always set a limit past which benchmarks don't matter. As long as you aren't Gates talking about 386's at least, that is something that is easily understandable by most people. If someone had said that 1 million elements was the limit for any set / list comparisons it would be difficult to argue with that. I wouldn't want to.

The problem i have with timeit is actually just side effects. The same issue comes into play with sets if you are prebuilding them. If I use timit to run my algorithm 10 times the first execution takes the most time, and it sorts the lists, later executions are faster but I don't want those in the results. I'm looking for avg to worst case results. In the case of comparing c code with byte code we've already given set comparisons a huge boost by choosing simple hashable items and a C implementation. trying to optimize it even further by using the least amount of statements possible starts to just be silly. I only said my algorithm crossed a threshold of speed at some number of elements. That should be expected of every algorithm. It's not an indictment of the set library or Python. Lots of perfectly good algorithms don't scale well, mine obviously doesn't scale small very well.

...

When I first wrote the algorithms(2000 or so) I compared them to [x for x in a if x in b] and I found that the later was faster. I didn't make sense at first but it was because the 'x in b' is done in C (I had just graduated and started using Python). If the data set was large enough I could see the big O growth was greater for the C version versus the python version. Similar to what we see here in the difference between the set operations and listex. I implemented listex in C and it was much faster at all data sizes over maybe 10 elements. I don't expect the same speedup compared to sets because they are more efficient. I also can't guarantee that the trend of set operations having a higher time growth will hold true for all data sizes. I only point it out and say for some use cases set relation operations aren't optimal, but they may be good enough. So far the benchmarks showed that that list implementation was slower than

and the results are (somewhat) comparable. If you design your own benchmarking tool (I do not think datetime is a good candidate though), anything you gain you lose on the reproducibility and comparability. Besides, saying this benchmark does not give the results I expect, would probably need also explaining what do you expect and why. the sets at every non-trivial case, sometimes by quite a margin. All the cases are trivial, small strings and some integers. When I run them there are differences. Even when you run them there are. Then you stop out the setup time so that set function are faster. Then I say that if you keep going the set gets beaten. Tim has already explained why, it also makes timsort so fast.

I am not saying that the C implementation cannot be faster, in fact, I will probably be eager to test it, if you come up with one. But after what I read (and posted) in this thread I am also reluctant to accept that C implementation _must_ be faster (or must be significantly faster). Maybe, your code, even when run in Python, is well optimized already, and won't get a significant speedup or will be 5x faster, but, honestly, I do not dare even to guess. The only way to prove it is to actually implement it in C. I've been busy lately but I should have something soon.

Considering your use case however, I wonder, if you would not be better going with the iterator approach (as Andrew has been hinting already for some time in his posts). Richard M. They will most likely have good performance on data sets that are close, but very poor on those that aren't balanced.

Andrew Barnert wrote:

On Sep 23, 2019, at 15:32, Richard Higginbotham higginbr@gmail.com wrote:

...

Considering your use case however, I wonder, if you would not be better going with the iterator approach (as Andrew has been hinting already for some time in his posts). Richard M. They will most likely have good performance on data sets that are close, but very poor on those that aren't balanced. The code you posted doesn’t do any galloping, it just advances the index one at a time. The fact that you could do approximate binary searches to optimize it doesn’t help if you never do those searches. So it’ll be exactly as poor on unbalanced Yes it probably will, but we won't be able to add binary searches using iterators. In which case, why use iterators... It's a pretty basic optimization step.

inputs as my Iterator code. After all, they’re exactly the same algorithm (except for trivial differences in how they handle one input or the other ending early); the only difference is that one implementation calls next and remembers the value, the other increases an index and indexes a list. I'm not bragging about my code. I think its neat, but I wrote it 20 years ago after graduating from college with a chemical engineering degree. It was my second python program and like 3rd or 4th program outside re-implementing the C library (as is common with students).

Of course if you always have lists already in memory, the added overhead of using an Iterator over the list is cost for no benefit. But that’s a fixed multiplier, it’s not different for balanced vs. unbalanced inputs. And if course if the Iterator ever allows you to avoid building an otherwise-unnecessary list, it’s a win, but that win is also a flat cost that depends only on the allocation time for N elements, which also doesn’t vary based on balanced vs. unbalanced inputs. Anyway, if your use case really is a gigantic directory from a filesystem that guarantees sorted order and it supports iterdir, iterators should help quite a bit.

In the spirit of comradery, I'll try to follow Steven D'Aprano's community advice and be a little more blunt. I'll skip the insults though. I wrote them but I took them out. Honestly, I could have done this at any time I just didn't want to hurt peoples feelings. I already converted it to C along time ago and did many many test I don't want to repeat. I know how it scales. We don't even have to convert to C. Let's just use pypy. For grins we'll change to an integer hash. For A not in B: trying A 1000, B 5000 best relcomp_set test time (msec): 0.009 best relcomp_set with set init test time (msec): 0.130 best relcomp_set with set init intersect test time (msec): 0.115 best list_relcomp test time (msec): 0.012 best sort test time (msec): 0.006 For A not in B: trying A 10000, B 50000 best relcomp_set test time (msec): 0.117 best relcomp_set with set init test time (msec): 2.448 best relcomp_set with set init intersect test time (msec): 2.649 best list_relcomp test time (msec): 0.077 best sort test time (msec): 0.048 For A not in B: trying A 1000000, B 5000000 best relcomp_set test time (msec): 82.131 best relcomp_set with set init test time (msec): 880.753 best relcomp_set with set init intersect test time (msec): 886.761 best list_relcomp test time (msec): 7.902 best sort test time (msec): 5.826 For A not in B: trying A 5000000, B 10000000 best relcomp_set test time (msec): 557.368 best relcomp_set with set init test time (msec): 3228.475 best relcomp_set with set init intersect test time (msec): 3725.047 best list_relcomp test time (msec): 25.626 best sort test time (msec): 13.632 Huh? At about 1000 elements they are equal but after that my 2nd python program is 10x faster, oops. Lets try more iterations "with a real Benchmark program". I won't repeat mine though well just take the first number that comes by. trying A 1000, B 5000 best relcomp_set test time (msec): 0.009 best relcomp_set with set init test time (msec): 0.116 best relcomp_set with set init intersect test time (msec): 0.118 best list_relcomp test time (msec): 0.015 best sort test time (msec): 0.006 For A not in B: trying A 10000, B 50000 best relcomp_set test time (msec): 0.115 best relcomp_set with set init test time (msec): 2.729 best relcomp_set with set init intersect test time (msec): 2.780 best list_relcomp test time (msec): 0.111 best sort test time (msec): 0.049 You don't want to see data sets higher than that. Ok, a little sarcasm but you earned it. All you had to do was not be jerks.

On Sun, Sep 22, 2019 at 8:25 PM Andrew Barnert <abarnert@yahoo.com> wrote:

One case I think you didn’t test is when the strings are generated in already-sorted order. In that case, as opposed to the case where you generate in random order and then sort, I think the PyUnicode objects and the actual character arrays will both be mostly contiguous (at least in a fresh process)—although I think the only way you could verify that is by using ctypes (or a C extension) to peek into the internal PyUnicode structs and look at the appropriate pointers. Anyway, the access pattern should more than be simple enough for the CPU to effectively cache-prefetch at all three levels, which could be a significant speedup for the sorted-list algorithms over the set algorithms.

I did not benchmark it, because the original code from the OP has an explicit sorting built-in, so I simply concluded this was not the case. Nevertheless...

And this isn’t entirely an artificial scenario; sometimes large numbers of strings really are generated in sorted order and in large batches like this—e.g., the filesystem, or a network client, or whatever is handing you data in sorted order and you put it right into a list of strings. So, it might be worth testing.

For the sake of completeness I did some benchmarks also with already sorted strings. I chose the following strings: In [3]: a = [f'String#{i:08}' for i in range(0, 20000000, 2)] In [4]: b = [f'String#{i:08}' for i in range(1, 20000001, 2)] In [5]: a[:5] Out[5]: ['String#00000000', 'String#00000002', 'String#00000004', 'String#00000006', 'String#00000008'] In [6]: b[:5] Out[6]: ['String#00000001', 'String#00000003', 'String#00000005', 'String#00000007', 'String#00000009'] First with the set ops: In [7]: timeit('list(set(a).difference(b))', number=1, globals=locals()) Out[7]: 3.9231181000000106 In [8]: timeit('list(set(a).difference(b))', number=1, globals=locals()) Out[8]: 2.642592999999991 In [9]: timeit('list(set(a).difference(b))', number=1, globals=locals()) Out[9]: 2.648031700000004 Does not really differ from the previous results. Then with the `list_relcomp` (note 2x `False` in the argument list to disable the sorting): In [10]: a = [f'String#{i:08}' for i in range(0, 20000000, 2)] In [11]: b = [f'String#{i:08}' for i in range(1, 20000001, 2)] In [12]: timeit('list_relcomp(a, b, False, False)', number=1, globals=locals()) Out[12]: 4.851956800000011 In [13]: timeit('list_relcomp(a, b, False, False)', number=1, globals=locals()) Out[13]: 4.8776169999999865 One interesting thing I noticed, when running `list_relcomp` with a trivial input, e.g. (where a = c, but in different objects): In [16]: a = [f'String#{i:08}' for i in range(0, 20000000, 2)] In [17]: c = [f'String#{i:08}' for i in range(0, 20000000, 2)] In [18]: timeit('list_relcomp(a, c, False, False)', number=1, globals=locals()) Out[18]: 2.8997035999999525 It ends up running much faster, because it does not have to build the resulting list (set implementation performance does not change much in this case) while in the first setup, everything in A goes into the result. So there are many details, but unless the use case can guarantee them, I am not sure they are worthy the speculations. But I think the real win for already-sorted data is laziness. With sets, at

least one of your data sets has to be strict, so you can put it in a set. With sorted lists, with a minor rewrite to the algorithms (which I posted earlier for intersection), you can use them directly on iterators instead. Imagine you’re reading 7GB worth of (already-sorted) strings and comparing to 2GB worth of strings on a machine with 8GB of RAM and plenty of swap space. Clearly the set, sorted list, or even anything clever that pandas might do, they’ll all throw your machine into swap hell, which will probably swamp the cost of using step-compare instead of sets and of using Iterators instead of lists. This one might be harder to benchmark (because the cost of the Iterator is going to end up threaded through the cost of the algorithm), but it seems like it should be a huge win over sets.

If you move everything to the iterators and maybe even dilute the operations over some async I/O it may be pretty effective, but when talking about the algorithm alone, I am not sure even the pre-sorted lists have an advantage, at least not in this implementation, maybe when implemented in C? Richard M.

Steve Jorgensen wrote:

What if, instead, there was an OrderedBag class that acts like a list and supports set operations. The advantage of this is that any hidden indexing that is used to optimize the operations could be efficiently created in the object that results from the set operation during its construction while performing the operation. Using lists, any such indexes would have to be produced and discarded for each operation (or could perhaps be kept in weak references or something like that, but that's messy). It seems like it would depend on the memory layout. If the items weren't stored in order then it would most likely suffer from cache misses the same way set operations do. I'm not sure if it would be slower than set operations in that case. Most likely there would be a curve in run time where sets were faster for some small number of items and slower for large collections similar to the list implementation. If you added binary searches it might be faster in the majority of cases but that's a lot of variables. The big question then becomes what criteria does it need to meet and is that quantified? It doesn't seem like that quantification is a consideration of this list. Unless you have a particular itch to scratch that is a lot of work. Adding enough general testing scenarios to satisfy a consensus is probably much much more.

Lets look at the test results from earlier for 50 million and 10 million item lists. For A not in B: trying A 1000000, B 5000000 best relcomp_set test time (msec): 82.131 best relcomp_set with set init test time (msec): 880.753 best relcomp_set with set init intersect test time (msec): 886.761 best list_relcomp test time (msec): 7.902 best sort test time (msec): 5.826 For A not in B: trying A 5000000, B 10000000 best relcomp_set test time (msec): 557.368 best relcomp_set with set init test time (msec): 3228.475 best relcomp_set with set init intersect test time (msec): 3725.047 best list_relcomp test time (msec): 25.626 best sort test time (msec): 13.632 Changing the order of set operations based on which set is largest is almost 10x the speed improvement. Should set operations be changed? It's probably faster no matter the order to convert them into lists and use my algorithm after about 10 million. In the end though we are still talking about a few seconds at most. If it worth it to you for that improvement that's one thing, but you should consider what you really need. Without clear performance/use case criteria I think you'll never leave the bike-shed here.