[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Raymond Hettinger]

Change by Raymond Hettinger :


--
resolution:  -> not a bug
stage:  -> 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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Tim Peters]

Tim Peters  added the comment:

For any fixed width integer type, the worst case of the dead simple loop (all 
bits are zero) is a fixed upper bound. So you don't mean "constant bounded" 
either. You mean something more like "clever C code that usually runs faster 
than the obvious loop".

See my "if it's not unbearably pedantic" comment earlier ;-) Again, by 
"primitive" I meant HW-level primitive. I agree that's not wholly clear from 
what I wrote, but really don't care - it's a trivial point that makes no 
difference in context. The lack of an integer type in C wide enough to support 
the division the paper uses is _the_ deal-breaker. That C doesn't define a 
count-leading-zero function either is just a flea on the tail of that dog.

--

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Barry Schwartz]

Barry Schwartz  added the comment:

I meant constant bounded

--

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Tim Peters]

Tim Peters  added the comment:

I'm not inclined to change anything here. It's a trivial point, and by 
"primitive" I had in mind a dedicated hardware instruction, blazing fast. Yes, 
I was aware of long-winded ways of doing it for specific fixed integer widths. 
But that's not what `O(1)` means. A dead obvious loop testing each bit, one at 
a time, starting with the MSB, until finding the first bit set, is also O(1) 
for any fixed-width int size.

So I'm not doing anything here. If someone else creates a PR with text they 
want to see instead, I'll review it, and if it's not unbearably pedantic ;-) 
I'll merge it.

--

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Barry Schwartz]

Barry Schwartz  added the comment:

Yes. Actually the issue is branching, not order of complexity, because looping 
at most 64 times is a linear-bounded operation. The methods I point out involve 
no branching! And so can be rather fast. I don't suggest they be used, but that 
the listsort.txt be revised.

--

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Presumably the OP is referring to this text:

"""
`powerloop()` emulates these divisions, 1 bit at a time, using comparisons,
subtractions, and shifts in a loop.

You'll notice the paper uses an O(1) method instead, but that relies on two
things we don't have:

- An O(1) "count leading zeroes" primitive. We can find such a thing as a C
  extension on most platforms, but not all, and there's no uniform spelling
  on the platforms that support it.

- Integer division on an integer type twice as wide as needed to hold the
  list length. But the latter is Py_ssize_t for us, and is typically the
  widest native signed integer type the platform supports.

But since runs in our algorithm are almost never very short, the once-per-run
overhead of `powerloop()` seems lost in the noise.

"""

--
assignee: docs@python -> tim.peters
nosy: +rhettinger

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Mark Dickinson]

Change by Mark Dickinson :


--
nosy: +tim.peters

___
Python tracker 

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

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Barry Schwartz]

New submission from Barry Schwartz :

The Objects/listsort.txt incorrectly implies that it is not possible to compute 
leading zero bits in O(1) time, using only standard C. For a fixed integer size 
it can be done, for instance, using de Bruijn sequences. See 
https://www.chessprogramming.org/BitScan

(The existence of such methods is not as widely known as it ought to be.)

--
assignee: docs@python
components: Documentation
messages: 411384
nosy: chemoelectric, docs@python
priority: normal
severity: normal
status: open
title: listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) 
time.
type: performance
versions: Python 3.11

___
Python tracker 

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