[issue8701] tarfile: first character of member names doubled

[Lars Gustäbel]

Changes by Lars Gustäbel :


--
assignee:  -> lars.gustaebel
nosy: +lars.gustaebel

___
Python tracker 

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

[issue8678] crashers in rgbimg

[Martin v . Löwis]

Martin v. Löwis  added the comment:

haypo: what's the relationship?

--

___
Python tracker 

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

[issue8699] Equality and hashing for functools.partial

[Daniel Urban]

Daniel Urban  added the comment:

Sorry, I realized I made a stupid mistake.  (I didn't use PyList_Sort to sort 
the list in partial_hash.)
Here is the corrected patch.

--
Added file: http://bugs.python.org/file17315/partial_eq_hash_2.diff

___
Python tracker 

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

[issue8701] tarfile: first character of member names doubled

[Lars Gustäbel]

Lars Gustäbel  added the comment:

Unfortunately, I cannot reproduce your problem and ask you to please provide 
more information. Would it be possible to attach the output or a screenshot 
depicting the problem? Which operating system/distribution do you use? Have you 
double-checked your testing conditions?

--

___
Python tracker 

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

[issue8673] configure script doesn't recognize 10.5 SDK correctly

[Ronald Oussoren]

Ronald Oussoren  added the comment:

The issue is indeed gone in HEAD. I've also verified the other 3 active 
branches.

--
resolution:  -> fixed
stage: needs patch -> committed/rejected
status: open -> closed

___
Python tracker 

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

[issue7724] setup.py ignores SDK root on OSX

[Ronald Oussoren]

Ronald Oussoren  added the comment:

The attached version should fix the issue found by Stefan. I'm going to do 
builds on OSX as well as Linux before committing though.

--
Added file: http://bugs.python.org/file17316/issue7724-v3.patch

___
Python tracker 

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

[issue8126] Python 3.1.2rc1 doesn't compile using the 10.4 sdk on a 10.6 Mac

[Ronald Oussoren]

Ronald Oussoren  added the comment:

I've verified that HEAD for both 3.1 and 3.2 build fine now, hence this issue 
can be closed.

--
resolution:  -> fixed
stage: needs patch -> committed/rejected
status: open -> closed

___
Python tracker 

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

[issue8702] difflib: unified_diff produces wrong patches (again)

[anatoly techtonik]

New submission from anatoly techtonik :

If source/target file for unified format diff context doesn't end with new 
line, the diff should contain this marker:

\ No newline at end of file

Or else there is information loss when such patch is applied.

http://en.wikipedia.org/wiki/Diff#Unified_format

--
components: Library (Lib)
messages: 105630
nosy: techtonik
priority: normal
severity: normal
status: open
title: difflib: unified_diff produces wrong patches (again)
versions: Python 2.6, Python 2.7, Python 3.1, Python 3.2, Python 3.3

___
Python tracker 

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

[issue8455] buildbot: test_urllib2_localnet failures (Connection refused) on Tiger buildbot

[Ronald Oussoren]

Changes by Ronald Oussoren :


--
assignee:  -> ronaldoussoren

___
Python tracker 

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

[issue8703] Py3k PyList_Type documentation mentions types.ListType

[Daniel Urban]

New submission from Daniel Urban :

The Py3k documentation of PyList_Type [1] contains the sentence:
"This is the same object as list and types.ListType in the Python layer."
But there is no types.ListType object in py3k.

[1] http://docs.python.org/dev/py3k/c-api/list.html#PyList_Type

--
assignee: d...@python
components: Documentation
messages: 105631
nosy: d...@python, durban
priority: normal
severity: normal
status: open
title: Py3k PyList_Type documentation mentions types.ListType
versions: Python 3.1, Python 3.2, Python 3.3

___
Python tracker 

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

[issue8702] difflib: unified_diff produces wrong patches (again)

[R. David Murray]

Changes by R. David Murray :


--
keywords: +easy
type:  -> behavior
versions:  -Python 3.3

___
Python tracker 

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

[issue8422] tiger buildbot: test_abspath_issue3426 failure (test_genericpath.py)

[Florent Xicluna]

Florent Xicluna  added the comment:

afaict, it needs backport to 2.7.

--
components: +Tests
nosy: +flox
stage:  -> commit review
status: closed -> open
type:  -> crash
versions: +Python 2.7 -Python 3.2

___
Python tracker 

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

[issue1481] test_uuid is warning about unreliable functions

[Stefan Krah]

Changes by Stefan Krah :


--
status: pending -> closed

___
Python tracker 

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

[issue6419] Broken test_kqueue.py on OpenBSD

[Stefan Krah]

Changes by Stefan Krah :


--
nosy: +skrah

___
Python tracker 

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

[issue8704] cgitb sends a bogus HTTP header if the app crashes before finishing headers

[Daniel Stutzbach]

New submission from Daniel Stutzbach :

If the CGI script crashes before finishing the headers, cgitb will emit invalid 
HTTP headers before showing the error message.  Below are HTTP headers I 
received, captured with a packet sniffer.  Note the "<--: spam".

HTTP/1.1 200 OK
Date: Thu, 13 May 2010 14:00:42 GMT
Server: Apache/2.2.9

[issue8704] cgitb sends a bogus HTTP header if the app crashes before finishing headers

[Daniel Stutzbach]

Changes by Daniel Stutzbach :


--
keywords: +easy

___
Python tracker 

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

[issue8702] difflib: unified_diff produces wrong patches (again)

[Mark Dickinson]

Mark Dickinson  added the comment:

I think difflib is behaving as intended here; changing to feature request.

Could you please clarify about the information loss?  I'm not seeing it.  As 
far as I can tell, the fact that unified_diff produces a list rather than a 
single string (as GNU diff effectively does) means that all necessary 
information about newlines is preserved, with no information loss:

newton:py3k dickinsm$ echo -n "one
two" > 1.txt
newton:py3k dickinsm$ echo -n "one
two 
" > 2.txt
newton:py3k dickinsm$ ./python.exe
Python 3.2a0 (py3k:81084:81085M, May 12 2010, 14:16:52) 
[GCC 4.2.1 (Apple Inc. build 5659)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from difflib import unified_diff
[47745 refs]
>>> list(unified_diff(list(open('1.txt')), list(open('2.txt'
['--- \n', '+++ \n', '@@ -1,2 +1,2 @@\n', ' one\n', '-two', '+two\n']
[53249 refs]

It looks to me as though the diff picks up the missing newline just fine.

The one problem with the above is that you can't do a ''.join() on it to give a 
meaningful diff, but I don't see that as a problem with the unified_diff 
function itself.

I'd be -1 on adding the "\ No newline at end of file" by default, since it 
complicates the unified_diff format unnecessarily (and would also affect 
backwards compatibility).  I wouldn't have any objections to an extra option 
for this, though.

--
nosy: +mark.dickinson
stage:  -> unit test needed
type: behavior -> feature request

___
Python tracker 

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

[issue8702] difflib: unified_diff produces wrong patches (again)

[Mark Dickinson]

Mark Dickinson  added the comment:

It turns out that this problem was already reported in issue 2142 (which has a 
patch);  closing as a duplicate.

--
resolution:  -> duplicate
status: open -> closed
superseder:  -> naive use of ''.join(difflib.unified_diff(...)) results in 
bogus diffs with inputs that don't end with end-of-line char (same with 
context_diff)

___
Python tracker 

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

[issue2142] naive use of ''.join(difflib.unified_diff(...)) results in bogus diffs with inputs that don't end with end-of-line char (same with context_diff)

[Mark Dickinson]

Mark Dickinson  added the comment:

Closed 8702 as a duplicate of this one.  Combining nosy lists.

--
nosy: +mark.dickinson, techtonik

___
Python tracker 

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

[issue2142] naive use of ''.join(difflib.unified_diff(...)) results in bogus diffs with inputs that don't end with end-of-line char (same with context_diff)

[Mark Dickinson]

Changes by Mark Dickinson :


--
versions: +Python 2.7, Python 3.2

___
Python tracker 

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

[issue7449] A number tests "crash" if python is compiled --without-threads

[Stefan Krah]

Stefan Krah  added the comment:

Victor, I think one more skip is required in test_socketserver.

--
nosy: +skrah
resolution: fixed -> 
status: closed -> open
Added file: 
http://bugs.python.org/file17317/nothreads-socketserver-shutdown.patch

___
Python tracker 

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

[issue2142] difflib.unified_diff(...) produces invalid patches

[anatoly techtonik]

anatoly techtonik  added the comment:

You mean that this patch sits in here for 2 years already? This suxx.

And nobody added the tag 'easy', because people haven't explicitly requested 
tracker privileges? That suxx. 

And it won't be in 2.7 because of that.. I am disappointed.

Why this issue is not labeled as 'difflib' related? How are people supposed to 
find this one?

--
title: naive use of ''.join(difflib.unified_diff(...)) results in bogus diffs 
with inputs that don't end with end-of-line char (same with context_diff) -> 
difflib.unified_diff(...) produces invalid patches

___
Python tracker 

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

[issue2142] difflib.unified_diff(...) produces invalid patches

[anatoly techtonik]

anatoly techtonik  added the comment:

Trent, the "\ New line..." seems to be feature specific to unified format only. 
http://en.wikipedia.org/wiki/Diff#Unified_format

--

___
Python tracker 

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

[issue4898] {context, unified}_diff add spurious trailing whitespace if fromfiledate/tofiledate are emptyk

[anatoly techtonik]

anatoly techtonik  added the comment:

Another 'easy' patch hangs for ages. =/

tag:easy
tag:difflib

--
nosy: +techtonik

___
Python tracker 

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

[issue7585] difflib should separate filename from timestamp with tab

[anatoly techtonik]

anatoly techtonik  added the comment:

tag:difflib

--

___
Python tracker 

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

[issue8422] tiger buildbot: test_abspath_issue3426 failure (test_genericpath.py)

[STINNER Victor]

STINNER Victor  added the comment:

> afaict, it needs backport to 2.7.

Right: r81135 (and r81137).

Blocked on 2.6 (it doesn't have the non-ASCII path test): r81139.

--
status: open -> closed

___
Python tracker 

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

[issue4898] {context, unified}_diff add spurious trailing whitespace if fromfiledate/tofiledate are emptyk

[anatoly techtonik]

anatoly techtonik  added the comment:

Thanks for the patch. This was fixed as part of issue 7585.

Please add issue 7585 as superceder and close this.

--

___
Python tracker 

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

[issue8084] pep-0370 on osx duplicates existing functionality

[Florent Xicluna]

Florent Xicluna  added the comment:

It fails on "x86 Tiger trunk" buildbot, too.
(the PPC Tiger buildbot is happy)

--
keywords: +buildbot
nosy: +flox

___
Python tracker 

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

[issue8699] Equality and hashing for functools.partial

[Daniel Urban]

Daniel Urban  added the comment:

On python-dev Yaniv Aknin pointed out that the keywords dictionary of a partial 
object is mutable [1].  This causes problems with hashing and equality.  The 
new patch replaces the keywords dictionary with a read-only proxy of that 
dictionary.  This seems to solve the problem. 

[1] http://mail.python.org/pipermail/python-dev/2010-May/100059.html

--
Added file: http://bugs.python.org/file17318/partial_eq_hash_3.diff

___
Python tracker 

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

[issue8705] shutil.rmtree with empty filepath

[Dan Koch]

New submission from Dan Koch :

The following sequence raises an exception, but nonetheless removes all files 
from the Desktop under Windows Vista.

import os, shutil, user

desktop_dir = os.path.join(user.home, 'Desktop')
os.chdir(desktop_dir)

shutil.rmtree('')

This does not occur under Fedora 12. Not tested on Mac OS X yet.

--
components: Windows
messages: 105646
nosy: dbkoch
priority: normal
severity: normal
status: open
title: shutil.rmtree with empty filepath
type: behavior
versions: Python 2.6

___
Python tracker 

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

[issue2142] difflib.unified_diff(...) produces invalid patches

[Mark Dickinson]

Mark Dickinson  added the comment:

Hmm.  Not in my version of diff:  it seems to use '\ No newline at end of file' 
for both unified and 'normal' diffs.

$ diff --version
diff (GNU diffutils) 2.8.1
Copyright (C) 2002 Free Software Foundation, Inc.
...

$ diff 1.txt 2.txt
2c2
< two
\ No newline at end of file
---
> two

--

___
Python tracker 

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

[issue8423] tiger buildbot: test_pep277 failures

[Florent Xicluna]

Changes by Florent Xicluna :


--
assignee:  -> ronaldoussoren
components: +Macintosh, Tests
nosy: +flox, mark.dickinson, michael.foord, ned.deily, ronaldoussoren
stage:  -> needs patch
type:  -> behavior
versions: +Python 2.7

___
Python tracker 

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

[issue8423] tiger buildbot: test_pep277 failures

[Florent Xicluna]

Florent Xicluna  added the comment:

Some diagnosis information ...

 - happens for 2 tests inside test_pep277: test_listdir and test_normalize
 - happens only for 4 weird filenames (added with #8180)
 - happens only on "x86 Tiger" buildbot ("PPC Tiger" does not report this error)

I've added some lines to regrtest.py to identify each platform:
"x86 Tiger": Darwin-8.10.1-i386-32bit little-endian (OS X 10.4.10)
"PPC Tiger": Darwin-8.11.0-Power_Macintosh-powerpc-32bit big-endian (OS X 
10.4.11)

I don't know how the endianness may be linked with this issue.


Failing files (4):
u'\u0385\u03d3\u03d4',
u'\u00a8\u0301\u03d2\u0301\u03d2\u0308',# == NFD(u'\u0385\u03d3\u03d4')
u'\u0020\u0308\u0301\u038e\u03ab',  # == NFKC(u'\u0385\u03d3\u03d4')
u'\u1e9b\u1fc1\u1fcd\u1fce\u1fcf\u1fdd\u1fde\u1fdf\u1fed',


One solution is to skip these files on all 'darwin' platforms, without losing 
more time on this issue.

--
assignee: ronaldoussoren -> 

___
Python tracker 

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

[issue8701] tarfile: first character of member names doubled

[Poor Yorick]

Poor Yorick  added the comment:

I can't reproduce it now, either.

--
status: open -> closed

___
Python tracker 

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

[issue3605] Py_FatalError causes infinite loop

[Jeffrey Yasskin]

Jeffrey Yasskin  added the comment:

Fixed in r81142.

--
resolution:  -> fixed
stage: patch review -> committed/rejected
status: open -> closed

___
Python tracker 

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

[issue8423] tiger buildbot: test_pep277 failures

[Ronald Oussoren]

Ronald Oussoren  added the comment:

It prefer if it were clear why these tests fail (but don't have time to look 
into this at the moment). That is, I don't mind if the tests get disabled on 
darwin, but only if there is a documented reason for it because otherwise 
disabling the test might hide a real issue.

--

___
Python tracker 

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

[issue8706] accept keyword arguments on all base type methods and builtins

[Gregory P. Smith]

New submission from Gregory P. Smith :

C Python has a real wart in that standard types and library functions that are 
implemented in C do not always accept keyword arguments:

>>> 'xx'.find('xx', 4)
4
>>> 'xx'.find('xx', start=4)
Traceback (most recent call last):
  File "", line 1, in 
TypeError: find() takes no keyword arguments
>>> 

While other things do accept keywords:

sorted(s, key=bla)


We should clean this up.  It is not well documented anywhere and I suspect 
other python implementations (haven't tested this) may accept keywords on these 
where C Python doesn't.

In string.find()'s case it looks like this is because it is an old style C 
method declaration that only gets an args tuple, no keyword args dict.

--
messages: 105652
nosy: gregory.p.smith
priority: normal
severity: normal
status: open
title: accept keyword arguments on all base type methods and builtins
type: feature request
versions: Python 3.2, Python 3.3

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

After experimenting with changing the order of the multiplications and not 
having much luck, I went back and looked for other differences in Alexander's 
Python functions that might cause the speed difference.  I believe 
partial_product2 is fast because it performs all of its operations in-place 
using a single list, whereas partial_product3 creates a new list during each 
iteration.  Here's a version of partial_product3 that operates in-place and is 
just as fast as partial_product2:

def partial_product3(j, i):
a = [l << 1 | 1 for l in range(j, i + 1)]
n = len(a)
while 1:
if n == 1:
return a[0]
half = n//2
for k in range(0,half):
a[k] = a[k*2] * a[k*2+1]
if n & 1:
a[half] = a[n-1]
n = half

--

___
Python tracker 

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

[issue8689] sqlite3 parameter substitution breaks with multiple parameters

[Marcin Bachry]

Marcin Bachry  added the comment:

I wrote a Perl script testing this issue and it fails too, so it's most 
probably a bug in sqlite itself.  I think the bug is already reported under id 
26ff0c82d1 in sqlite bug tracker: http://www.sqlite.org/src/rptview?rn=2

--
nosy: +marcin.bachry

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

Daniel,

Your variant does not seem to work:

>>> def partial_product3(j, i):
... a = [l << 1 | 1 for l in range(j, i + 1)]
... n = len(a)
... while 1:
... if n == 1:
... return a[0]
... half = n//2
... for k in range(0,half):
... a[k] = a[k*2] * a[k*2+1]
... if n & 1:
... a[half] = a[n-1]
... n = half

>>> partial_product3(4,6)
99
>>> 9 * 11 * 13
1287

but it looks like I posted a buggy version of partial_product2 as well.  
Strange because I thought I had enough doctests to catch the errors.  I'll redo 
the testing.

--

___
Python tracker 

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

[issue8670] c_types.c_wchar should not assume that sizeof(wchar_t) == sizeof(Py_UNICODE)

[STINNER Victor]

STINNER Victor  added the comment:

Support of characters outside the Unicode BMP (code > 0x) is not complete 
in narrow build (sizeof(Py_UNICODE) == 2) for Python2:

$ ./python
Python 2.7b2+ (trunk:81139M, May 13 2010, 18:45:37) 
>>> x=u'\U0001'
>>> x[0], x[1]
(u'\ud800', u'\udc00')
>>> len(x)
2
>>> ord(x)
Traceback (most recent call last):
  ...
TypeError: ord() expected a character, but string of length 2 found
>>> unichr(0x1)
Traceback (most recent call last):
  ...
ValueError: unichr() arg not in range(0x1) (narrow Python build)

It looks better in Python3:

$ ./python 
Python 3.2a0 (py3k:81137:81138, May 13 2010, 18:50:51) 
>>> x='\U0001'
>>> x[0], x[1]
('\ud800', '\udc00')
>>> len(x)
2
>>> ord(x)
65536
>>> chr(0x1)
'\U0001'

About the issue, the problem is in function u_set(). This function should use 
PyUnicode_AsWideChar() but PyUnicode_AsWideChar() doesn't support surrogates... 
whereas PyUnicode_FromWideChar() does support surrogates.

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

Isn't it amazing how fast one can make incorrect code? ;-)

Here is a fixed version of my partial_product3, but now it is no faster than 
partial_product.

def partial_product3(j, i):
a = [l << 1 | 1 for l in range(j, i + 1)]
n = len(a)
while 1:
if n == 1:
return a[0]
half = n//2
for k in range(0,half):
a[k] = a[k*2] * a[k*2+1]
if n & 1:
a[half] = a[n-1]
n = half + 1
else:
n = half

--

___
Python tracker 

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

[issue8703] Py3k PyList_Type documentation mentions types.ListType

[Benjamin Peterson]

Benjamin Peterson  added the comment:

Fixed in r81145. Thanks.

--
nosy: +benjamin.peterson
resolution:  -> fixed
status: open -> closed

___
Python tracker 

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

[issue1100562] deepcopying listlike and dictlike objects

[Michele Orrù]

Michele Orrù  added the comment:

Unit tests added; tested both on python2.6 and python2.7.

--
nosy: +maker
versions: +Python 2.6
Added file: http://bugs.python.org/file17319/issue1100562.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Mark Dickinson]

Mark Dickinson  added the comment:

Does anyone feel like doing a speed comparison between Daniel's C patch and a 
version with a direct no-frills iterative version of factorial_part_product 
(i.e., just a simple  'for (i = n; i <= m; i += 2) {  }?  I have a sneaking suspicion that the iterative version will be faster 
even for quite large values of n, but I'd be happy to be proven wrong.

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Mark Dickinson]

Mark Dickinson  added the comment:

And why are we trying to speed up the pure Python factorial code here?  I don't 
imagine that those speed differences are going to translate well to C.

--

___
Python tracker 

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

[issue8423] tiger buildbot: test_pep277 failures

[Mark Dickinson]

Mark Dickinson  added the comment:

> It prefer if it were clear why these tests fail

I agree.  There's little point having tests if we're just going to disable them 
when they fail without understanding why they're failing first.

At that point a green buildbot just means "Hey, we disabled all failing 
tests!", rather than being an indication that Python's working well on that 
platform.

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

On Thu, May 13, 2010 at 5:31 PM, Mark Dickinson  wrote:
> And why are we trying to speed up the pure Python factorial code here?

I would expect that for large factorials the performance will be
determined by the number of long multiplications and the size of
multiplicands.

> I don't imagine that those speed differences are going to translate well to 
>C.

The differences between recursive and non-recursive versions are not
likely to translate well, but the difference (if any) between the
order of multiplication most likely will.

In any case, I am attaching fixed version of factorial4.

$ ./python.exe -m timeit -s "from factorial4 import f0 as f" "f(1)"
10 loops, best of 3: 65.5 msec per loop
$ ./python.exe -m timeit -s "from factorial4 import f1 as f" "f(1)"
10 loops, best of 3: 66.9 msec per loop
$ ./python.exe -m timeit -s "from factorial4 import f2 as f" "f(1)"
10 loops, best of 3: 56.5 msec per loop
$ ./python.exe -m timeit -s "from factorial4 import f3 as f" "f(1)"
10 loops, best of 3: 63 msec per loop

--
Added file: http://bugs.python.org/file17320/factorial4.py

___
Python tracker 

___import functools
import operator

product = functools.partial(functools.reduce, operator.mul)


def partial_product(j, i):
if i == j:
return j << 1 | 1
if i == j + 1:
return (j << 1 | 1) * (i << 1 | 1)
l = i + j >> 1
return partial_product(j, l) * partial_product(l + 1, i)

def naive_factorial(n):
"""Naive implementation of factorial: product([1, ..., n])

>>> naive_factorial(4)
24
"""
return product(range(1, n+1), 1)

def factorial(n, pp=partial_product):
"""Implementation of Binary-Split Factorial algorithm

See http://www.luschny.de/math/factorial/binarysplitfact.html

>>> for n in range(20):
... assert(factorial(n) == naive_factorial(n))
>>> import math
>>> assert(factorial(100) == math.factorial(100))
"""
_, r = loop(n, pp)
return r << (n - count_bits(n))

def loop(n, pp):
p = r = 1
for i in range(n.bit_length() - 2, -1, -1):
m = n >> i
if m > 2:
p *= pp(((m >> 1) + 1) >> 1, (m - 1) >> 1)
r *= p
return p, r

def partial_product1(j, i):
return product((l << 1 | 1 for l in range(j, i + 1)), 1)

def partial_product2(j, i):
a = [l << 1 | 1 for l in range(j, i + 1)]
n = i - j + 1
p = 1
while n > 1:
for k in range(n>>1):
a[k] *= a[n-k-1]
n = (n>>1) + (n&1)
return a[0]

def partial_product3(j, i):
a = [l << 1 | 1 for l in range(j, i + 1)]
while 1:
n = len(a)
if n == 1:
return a[0]
a = [a[k<<1] * a[k<<1|1] for k in range(n>>1)] + a[(n >> 1)<<1:]

def partial_product4(j, i):
if i == j:
return j << 1 | 1
if i == j + 1:
return (j << 1 | 1) * (i << 1 | 1)
return (j << 1 | 1) * (i << 1 | 1) * partial_product4(j + 1, i - 1)


def count_bits(n):
count = 0
while n:
n &= n - 1
count += 1
return count

def f0(n):
return factorial(n)

def f1(n):
return factorial(n, partial_product1)

def f2(n):
return factorial(n, partial_product2)

def f3(n):
return factorial(n, partial_product3)


if __name__ == '__main__':
for n in list(range(12, 20)) + [100, 101, 200]:
assert(f0(n) == f1(n) == f2(n) == f3(n))
import doctest
doctest.testmod()
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


Removed file: http://bugs.python.org/file17313/factorial4.py

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Mark Dickinson]

Mark Dickinson  added the comment:

> I would expect that for large factorials the performance will be
> determined by the number of long multiplications and the size of
> multiplicands.

Okay, but I don't think we should care about the performance of *really* large 
factorials for Python.  People who care about every bit of speed in that 
situation should be using GMP or something similar.  An optimization that only 
makes a difference for (say) factorial(5) or higher isn't going to make 
much difference to most Python users.  Optimizations that speed up, say, 
factorial(n) for n <= 1000 would seem more valuable.

> The differences between recursive and non-recursive versions are not
> likely to translate well, but the difference (if any) between the
> order of multiplication most likely will.

Perhaps.  But the differences between the various Python versions here are 
small enough that they could easily be swamped by other factors involved in the 
Python-to-C translation.

We already have a working C patch here (modulo minor issues), and I'd like to 
move forward with that patch;  I think this issue discussion is getting a bit 
side-tracked.

grumpily-yours...

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

Speaking of getting side-tracked, I didn't see an answer to a question I asked 
earlier.  I'd like to get some feedback before I proceed with revising the 
patch.

For the find-last-set-bit (to replace log2) and count-set-bits operations, 
would it be worthwhile to create a pybits.h and .c that defines 
_Py_FindLastSetBit and _Py_CountSetBits? (with appropriate logic in the .h and 
configure.in to use system/compiler versions if available)

There are already two implementations of find-last-set-bit in Python:
bits_in_digit() in Objects/longobject.c and hi0bits() in Python/dtoa.c, which I 
could consolidate.

Alternately, I could just add static functions to mathmodule.c with the 
simplest possible implementation (they're only called once per factorial, so 
the performance impact is minimal).

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

On Thu, May 13, 2010 at 6:09 PM, Daniel Stutzbach
 wrote:
..
> Speaking of getting side-tracked, I didn't see an answer to a question I asked
> earlier.  I'd like to get some feedback before I proceed with revising the 
> patch.

I did not respond because I don't have an answer. :-)  Maybe it is
time to revisit Raymond's reasoning in msg63969 where he argued that
factorial should be an int method because it would benefit from access
to integer implementation details.

He also argued that
"""
Compared to  numbits() and isqrt(), a factorial() method is more basic
in that it is self explanatory and everyone knows what it means by the
time they are in middle school.
"""
nevertheless numbits() aka bit_length() has become an int method, but
factorial landed in math.

>
> For the find-last-set-bit (to replace log2) and count-set-bits operations, 
> would it
> be worthwhile to create a pybits.h and .c that defines _Py_FindLastSetBit and 
> >_Py_CountSetBits? (with appropriate logic in the .h and configure.in to use
> system/compiler versions if available)

Since it is unlikely that either factorial() or bit_length() will be
moved from their current location, I would be +1 on creating pybits.
I would give them different names, though.  Popcount seems to be the
most popular name for CountSetBits and instead of FindLastSetBit, a
more common function seems to be nlz, number of leading zeros.  On the
other hand, since  bit_length is already established, maybe
_Py_bit_length_long(long) and (if needed) _Py_bit_length_int(int)
would make sense.

>
> There are already two implementations of find-last-set-bit in Python:
> bits_in_digit() in Objects/longobject.c and hi0bits() in Python/dtoa.c,
> which I could consolidate.

How did you find it?!  I hope we'll end up with a better name than that.

>
> Alternately, I could just add static functions to mathmodule.c with the 
> simplest
> possible implementation (they're only called once per factorial, so the
> performance impact is minimal).

In the scope of this issue I would say do that.  Pybits proposal seem
to deserve it's own issue.

--

___
Python tracker 

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

[issue1100562] deepcopying listlike and dictlike objects

[Ezio Melotti]

Changes by Ezio Melotti :


--
components: +Library (Lib) -None
nosy: +ezio.melotti
stage: unit test needed -> patch review

___
Python tracker 

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

[issue8707] Duplicated document in telnetlib.

[INADA Naoki]

New submission from INADA Naoki :

http://docs.python.org/dev/library/telnetlib.html#telnetlib.Telnet

The part "number can be passed to the constructor... " is duplicated.

--
assignee: d...@python
components: Documentation
messages: 105667
nosy: d...@python, naoki
priority: normal
severity: normal
status: open
title: Duplicated document in telnetlib.
versions: Python 2.7

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

On Wed, May 12, 2010 at 3:47 PM, Mark Dickinson  wrote:
>...
> Realistically though, I don't see an iterative version of 
> factorial_part_product as
> an option for the C patch, without a significant increase in complexity. 
>  Daniel's
> current patch is remarkably clean and simple, and I'd like to keep it that 
> way.
>

I am attaching an iterative version in C patch.  I don't think it
represents a dramatic increase in complexity ~ 40 lines over Daniel's
30.

> I did think about various evil schemes for an iterative version, ...

I would not say my patch is evil, maybe a bit naughty. :-) It can be
made less evil by resizing the list instead of filling its tail with
NULLs or more evil by using a tuple instead of list.

The performance  appears to be identical to Daniel's with no small
integer multiplication optimization.  The later gives about 2%
improvement.

--
Added file: http://bugs.python.org/file17321/factorial-no-recursion.patch

___
Python tracker 

___Index: Modules/mathmodule.c
===
--- Modules/mathmodule.c(revision 81150)
+++ Modules/mathmodule.c(working copy)
@@ -1129,56 +1129,173 @@
 Return an accurate floating point sum of values in the iterable.\n\
 Assumes IEEE-754 floating point arithmetic.");
 
+/* Divide-and-conquer factorial algorithm
+ *
+ * Based on the formula and psuedo-code provided at:
+ * http://www.luschny.de/math/factorial/binarysplitfact.html
+ *
+ * Faster algorithms exist, but they're more complicated and depend on
+ * a fast prime factoriazation algorithm.
+ */
+
+/* i-th odd number */
+#define ODD(i) (i << 1 | 1) 
+/* Compute product(ODD(i) for i in range(first, last+1)) */
 static PyObject *
+factorial_partial_product(unsigned long first, unsigned long last)
+{
+PyObject *result;
+PyObject *a, *x, *y;
+Py_ssize_t n, i;
+
+n = last - first + 1;
+if (n <= 0)
+   return PyLong_FromLong(1L);
+if (n == 1)
+   return PyLong_FromUnsignedLong(ODD(first));
+
+/* a = [ODD(i) for i in range(first, last + 1)] */
+a = PyList_New(last - first + 1);
+if (a == NULL)
+   return NULL;
+for  (i = 0; i < n; ++i) {
+   result = PyLong_FromUnsignedLong(ODD(first + i));
+   if (result == NULL)
+   goto done;
+   PyList_SET_ITEM(a, i, result);
+}
+while (n > 1) {
+   for (i = (n >> 1) - 1; i >= 0; --i) {
+   x = PyList_GET_ITEM(a, i);
+   y = PyList_GET_ITEM(a, n - i - 1);
+   result = PyNumber_Multiply(x, y);
+   if (result == NULL)
+   goto done;
+   PyList_SET_ITEM(a, i, result);
+   PyList_SET_ITEM(a, n - i - 1, NULL);
+   Py_DECREF(x);
+   Py_DECREF(y);
+   }
+   n = (n >> 1) + (n & 1);
+}
+/* Release reference held by the list */
+PyList_SET_ITEM(a, 0, NULL);
+ done:
+Py_DECREF(a);
+return result;
+}
+
+static unsigned long
+bit_length(unsigned long n)
+{
+unsigned long len = 0;
+while (n != 0) {
+   ++len;
+   n >>= 1;
+}
+return len;
+}
+
+static unsigned long
+bit_count(unsigned long n)
+{
+unsigned long count = 0;
+while (n != 0) {
+   ++count;
+   n &= n - 1; /* clear least significant bit */
+}
+return count;
+}
+
+static PyObject *
+factorial_loop(unsigned long n)
+{
+long i, v;
+PyObject *p, *r;
+PyObject *part, *tmp;
+
+p = PyLong_FromLong(1L);
+if (p == NULL)
+return NULL;
+Py_INCREF(p);
+r = p;
+
+for (i = bit_length(n) - 2; i >= 0; --i) {
+v = n >> i;
+if (v > 2) {
+   part = factorial_partial_product(((v >> 1) + 1) >> 1, (v - 1) >> 1);
+   if (part == NULL)
+   goto error;
+
+   tmp = PyNumber_Multiply(p, part);
+   Py_DECREF(part);
+   if (tmp == NULL)
+   goto error;
+   Py_DECREF(p);
+   p = tmp;
+
+   tmp = PyNumber_Multiply(r, p);
+   if (tmp == NULL)
+   goto error;
+   Py_DECREF(r);
+   r = tmp;
+   }
+}
+Py_DECREF(p);
+return r;
+ error:
+Py_DECREF(p);
+Py_DECREF(r);
+return NULL;
+}
+
+static PyObject *
 math_factorial(PyObject *self, PyObject *arg)
 {
-long i, x;
-PyObject *result, *iobj, *newresult;
+PyObject *result;
 
+PyObject *r; /* result without trailing zeros */
+PyObject *ntz; /* number of trailing zeros */
+long n;
+
 if (PyFloat_Check(arg)) {
-PyObject *lx;
 double dx = PyFloat_AS_DOUBLE((PyFloatObject *)arg);
 if (!(Py_IS_FINITE(dx) && dx == floor(dx))) {
 PyErr_SetString(PyExc_ValueError,
 "factorial() only accepts integral values");
 return NULL;
 }
-lx = PyLong_FromDouble(dx);

[issue8423] tiger buildbot: test_pep277 failures

[Florent Xicluna]

Florent Xicluna  added the comment:

The gory details...

>>> import os, unicodedata
>>> tempdir = u'temp_pep277'
>>> name = u'\u0385\u03d3\u03d4'
>>> os.mkdir(tempdir)
>>> with open(os.path.join(tempdir, name), 'w') as f:
... f.write('foo')
>>> unicodedata.normalize('NFD', name)
u'\xa8\u0301\u03d2\u0301\u03d2\u0308'
>>> os.listdir(tempdir)
[u'\xa8\u0301\u03d2\u03d2\u0301\u0308']

The filename should use the Normal Decomposition (NFD) of the original 
filename. But the decomposition looks wrong on this platform.

The problem is similar for the other special filenames. Examples:
- u'\u0385\u03d3\u03d4'
 ==> NFD: u'\xa8\u0301\u03d2\u0301\u03d2\u0308'
 ==> OSX: u'\xa8\u0301\u03d2\u03d2\u0301\u0308'
- u' \u0308\u0301\u038e\u03ab'
 ==> NFD: u' \u0308\u0301\u03a5\u0301\u03a5\u0308'
 ==> OSX: u' \u0308\u0301\u03a5\u03a5\u0301\u0308'
- u'\u1e9b\u1fc1\u1fcd\u1fce\u1fcf\u1fdd\u1fde\u1fdf\u1fed'
 ==> NFD: 
u'\u017f\u0307\xa8\u0342\u1fbf\u0300\u1fbf\u0301\u1fbf\u0342\u1ffe\u0300\u1ffe\u0301\u1ffe\u0342\xa8\u0300'
 ==> OSX: 
u'\u017f\u0307\xa8\u0342\u1fbf\u0300\u1fbf\u0301\u1fbf\u1ffe\u1ffe\u1ffe\xa8\u0342\u0300\u0301\u0342\u0300'

I have no idea how to investigate further.
And the "PPC Tiger" buildbot does not fail here.

Reference about OSX decomposition:
http://developer.apple.com/mac/library/qa/qa2001/qa1173.html

--

___
Python tracker 

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

[issue8670] c_types.c_wchar should not assume that sizeof(wchar_t) == sizeof(Py_UNICODE)

[STINNER Victor]

STINNER Victor  added the comment:

Patch for Python3:
 - Fix PyUnicode_AsWideChar() to support surrogates (Py_UNICODE: 2 bytes, 
wchar_t: 4 bytes)
 - u_set() of _ctypes uses PyUnicode_AsWideChar()
 - add a test (skipped if sizeof(wchar_t) is smaller than 4 bytes)

It's too late to fix Python2: 2.7 beta 2 was released (it doesn't support non 
BMP characters for chr()/ord()).

TODO:
 - I'm not sure that my patch on PyUnicode_AsWideChar() works if 
sizeof(wchar_t)==2
 - Test the patch on Windows
 - Check that it doesn't break other functions calling PyUnicode_AsWideChar()

ctypes, _locale.strcoll() and time.strftime() use PyUnicode_AsWideChar(). time 
has interesting comments:

/* This assumes that PyUnicode_AsWideChar doesn't do any UTF-16
   expansion. */
if (PyUnicode_AsWideChar((PyUnicodeObject*)format,
 (wchar_t*)PyBytes_AS_STRING(tmpfmt),
 PyUnicode_GetSize(format)+1) == (size_t)-1)
/* This shouldn't fail. */
Py_FatalError("PyUnicode_AsWideChar failed");

--
keywords: +patch
Added file: 
http://bugs.python.org/file17322/pyunicode_aswidechar_surrogates-py3k.patch

___
Python tracker 

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

[issue8584] test_multiprocessing skips some tests

[Brian Curtin]

Brian Curtin  added the comment:

Value and copy come from multiprocessing.sharedctypes, not from ctypes. Changed 
the import and also the test skipping based on this.

(done during a presentation with the Chicago Python Users Group)

--
keywords: +patch
nosy: +brian.curtin
Added file: http://bugs.python.org/file17323/issue8584.diff

___
Python tracker 

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

[issue8584] test_multiprocessing skips some tests

[Brian Curtin]

Changes by Brian Curtin :


--
keywords: +needs review
stage: needs patch -> patch review

___
Python tracker 

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

[issue8708] OpenID blunder

[Jack Diederich]

New submission from Jack Diederich :

I tried logging into the tracker using my gmail login and accidentally
created a new user.  Could someone either wipe out the OpenID for
jackd...@gmail.com (but NOT the "jackdied" login with email addy of
jackd...@gmail.com) or combine the two?

In the end I just reset my password and logged in as the original "jackdied"

TIA,

-Jack

--
messages: 105672
nosy: Jack.Diederich
priority: normal
severity: normal
status: open
title: OpenID blunder

___
Python tracker 

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

[issue8707] Duplicated document in telnetlib.

[Jack Diederich]

Changes by Jack Diederich :


--
assignee: d...@python -> jackdied
nosy: +jackdied

___
Python tracker 

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

[issue8708] OpenID blunder

[Jack Diederich]

Jack Diederich  added the comment:

Woops, didn't know that email would create a new bug.

--
nosy: +jackdied

___
Python tracker 

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

[issue8423] tiger buildbot: test_pep277 failures

[STINNER Victor]

STINNER Victor  added the comment:

> Reference about OSX decomposition:
> http://developer.apple.com/mac/library/qa/qa2001/qa1173.html

Mac OS X source code:
http://www.opensource.apple.com/source/xnu/xnu-1504.3.12/bsd/vfs/vfs_utfconv.c?txt

--

___
Python tracker 

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

[issue4653] Patch to fix typos for Py3K

[STINNER Victor]

STINNER Victor  added the comment:

I fixed the typo in pythonrun.c: r81156. I don't use Windows, so I cannot 
review the other fixes.

--

___
Python tracker 

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

[issue8256] input() doesn't catch _PyUnicode_AsString() exception; io.StringIO().encoding is None

[STINNER Victor]

STINNER Victor  added the comment:

Here is a patch catching the _PyUnicode_AsString() error.

input() uses sys.stdout.encoding to encode the prompt to a byte string, but 
PyOS_StdioReadline() writes the prompt to stderr (it should use sys_stdout).

I don't know which encoding should be used if sys.stdout.encoding is None (eg. 
if sys.stdout is a StringIO() object).

StringIO() of _io module has no encoding because it stores unicode characters, 
not bytes. StringIO() of _pyio module is based on BytesIO() and use utf8 
encoding, but the reference implementation is now _io.

--
Added file: http://bugs.python.org/file17324/input_stdout_encoding.patch

___
Python tracker 

___Index: Python/bltinmodule.c
===
--- Python/bltinmodule.c(révision 81157)
+++ Python/bltinmodule.c(copie de travail)
@@ -1618,6 +1618,7 @@
 if (promptarg != NULL) {
 PyObject *stringpo;
 PyObject *stdout_encoding;
+char *stdout_encoding_str;
 stdout_encoding = PyObject_GetAttrString(fout,
  "encoding");
 if (stdout_encoding == NULL) {
@@ -1630,8 +1631,17 @@
 Py_DECREF(stdout_encoding);
 return NULL;
 }
+if (stdout_encoding != Py_None)
+stdout_encoding_str = _PyUnicode_AsString(stdout_encoding);
+else
+stdout_encoding_str = "utf-8";
+if (stdout_encoding_str == NULL) {
+Py_DECREF(stdin_encoding);
+Py_DECREF(stdout_encoding);
+return NULL;
+}
 po = PyUnicode_AsEncodedString(stringpo,
-_PyUnicode_AsString(stdout_encoding), NULL);
+   stdout_encoding_str, NULL);
 Py_DECREF(stdout_encoding);
 Py_DECREF(stringpo);
 if (po == NULL) {
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue5099] subprocess.Popen.__del__ causes AttributeError (os module == None)

[Brett Cannon]

Brett Cannon  added the comment:

OK, my patch is committed:

 2.6 81158
 2.7 81154
 3.1 81159
 3.2 81155

I didn't apply your test, Gabriel, as it passed without the fixes. Thanks to 
the work you did on it, though.

--
resolution:  -> fixed
status: open -> closed

___
Python tracker 

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

[issue8698] PEP 391: Adding documentation of logging.config.dictConfig

[Dan Buch]

Changes by Dan Buch :


--
nosy: +meatballhat

___
Python tracker 

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

[issue2142] difflib.unified_diff(...) produces invalid patches

[Dan Buch]

Changes by Dan Buch :


--
nosy: +meatballhat

___
Python tracker 

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

[issue8704] cgitb sends a bogus HTTP header if the app crashes before finishing headers

[Dan Buch]

Changes by Dan Buch :


--
nosy: +meatballhat

___
Python tracker 

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

[issue8706] accept keyword arguments on all base type methods and builtins

[Dan Buch]

Changes by Dan Buch :


--
nosy: +meatballhat

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

On Thu, May 13, 2010 at 5:58 PM, Mark Dickinson  wrote:
> Optimizations that speed up, say, factorial(n) for n <= 1000 would seem more 
>valuable.

I am attaching a variant of my patch which precomputes partial
products that fit in 32 bit unsigned int.  This results in speed up
over Daniel's code which varies from 1.8x for 20! down to 7% for 100!
and no measurable improvement for 1000!.

This optimization is orthogonal to the choice of partial_product
algorithm and can be easily extended on platforms with long long to
precompute 64 bit products.

--
Added file: http://bugs.python.org/file17325/factorial-precompute-partials.patch

___
Python tracker 

___Index: Modules/mathmodule.c
===
--- Modules/mathmodule.c(revision 81150)
+++ Modules/mathmodule.c(working copy)
@@ -1129,56 +1129,183 @@
 Return an accurate floating point sum of values in the iterable.\n\
 Assumes IEEE-754 floating point arithmetic.");
 
+/* Divide-and-conquer factorial algorithm
+ *
+ * Based on the formula and psuedo-code provided at:
+ * http://www.luschny.de/math/factorial/binarysplitfact.html
+ *
+ * Faster algorithms exist, but they're more complicated and depend on
+ * a fast prime factoriazation algorithm.
+ */
+
+static unsigned long 
+precomputed[] = {3, 15, 5, 35, 315, 63, 693, 9009, 1287, 19305, 328185, 36465, 
692835,
+14549535, 1322685, 30421755, 760543875, 58503375, 
1579591125ul, 3053876175ul};
+/* i-th odd number */
+#define ODD(i) (((i) << 1) | 1) 
+/* Compute product(ODD(i) for i in range(first, last+1)) */
 static PyObject *
+factorial_partial_product(unsigned long first, unsigned long last)
+{
+PyObject *result;
+PyObject *a, *x, *y;
+Py_ssize_t n, i;
+
+if (last < sizeof(precomputed)/sizeof(*precomputed)) {
+   size_t index = first + last - 2;
+   if (index <  sizeof(precomputed)/sizeof(*precomputed)) {
+   return PyLong_FromUnsignedLong(precomputed[index]);
+   }
+}
+   
+n = last - first + 1;
+if (n <= 0)
+   return PyLong_FromLong(1L);
+if (n == 1)
+   return PyLong_FromUnsignedLong(ODD(first));
+
+/* a = [ODD(i) for i in range(first, last + 1)] */
+a = PyList_New(last - first + 1);
+if (a == NULL)
+   return NULL;
+for  (i = 0; i < n; ++i) {
+   result = PyLong_FromUnsignedLong(ODD(first + i));
+   if (result == NULL)
+   goto done;
+   PyList_SET_ITEM(a, i, result);
+}
+while (n > 1) {
+   for (i = (n >> 1) - 1; i >= 0; --i) {
+   x = PyList_GET_ITEM(a, i);
+   y = PyList_GET_ITEM(a, n - i - 1);
+   result = PyNumber_Multiply(x, y);
+   if (result == NULL)
+   goto done;
+   PyList_SET_ITEM(a, i, result);
+   PyList_SET_ITEM(a, n - i - 1, NULL);
+   Py_DECREF(x);
+   Py_DECREF(y);
+   }
+   n = (n >> 1) + (n & 1);
+}
+/* Release reference held by the list */
+PyList_SET_ITEM(a, 0, NULL);
+ done:
+Py_DECREF(a);
+return result;
+}
+
+static unsigned long
+bit_length(unsigned long n)
+{
+unsigned long len = 0;
+while (n != 0) {
+   ++len;
+   n >>= 1;
+}
+return len;
+}
+
+static unsigned long
+bit_count(unsigned long n)
+{
+unsigned long count = 0;
+while (n != 0) {
+   ++count;
+   n &= n - 1; /* clear least significant bit */
+}
+return count;
+}
+
+static PyObject *
+factorial_loop(unsigned long n)
+{
+long i, v;
+PyObject *p, *r;
+PyObject *part, *tmp;
+
+p = PyLong_FromLong(1L);
+if (p == NULL)
+return NULL;
+Py_INCREF(p);
+r = p;
+
+for (i = bit_length(n) - 2; i >= 0; --i) {
+v = n >> i;
+if (v > 2) {
+   part = factorial_partial_product(((v >> 1) + 1) >> 1, (v - 1) >> 1);
+   if (part == NULL)
+   goto error;
+
+   tmp = PyNumber_Multiply(p, part);
+   Py_DECREF(part);
+   if (tmp == NULL)
+   goto error;
+   Py_DECREF(p);
+   p = tmp;
+
+   tmp = PyNumber_Multiply(r, p);
+   if (tmp == NULL)
+   goto error;
+   Py_DECREF(r);
+   r = tmp;
+   }
+}
+Py_DECREF(p);
+return r;
+ error:
+Py_DECREF(p);
+Py_DECREF(r);
+return NULL;
+}
+
+static PyObject *
 math_factorial(PyObject *self, PyObject *arg)
 {
-long i, x;
-PyObject *result, *iobj, *newresult;
+PyObject *result;
 
+PyObject *r; /* result without trailing zeros */
+PyObject *ntz; /* number of trailing zeros */
+long n;
+
 if (PyFloat_Check(arg)) {
-PyObject *lx;
 double dx = PyFloat_AS_DOUBLE((PyFloatObject *)arg);
 if (!(Py_IS_FINITE(dx) && dx == floor(dx))) {
 PyErr_SetString

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

That's a clever idea.  Do you have a Python script that generates the
precomputed values?

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

It's a little too clever though.  It gives the wrong answer for 29!.

I'll have a revised version of my patch done sometime tomorrow.

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

Oh, my!

How did that last term get into precomputed list?!

It should have been 

precomputed[] = {3, 15, 5, 35, 315, 63, 693, 9009, 1287, 19305, 328185, 36465, 
692835,
 14549535, 1322685, 30421755, 760543875, 58503375, 
1579591125ul};

The next term is 36 bit
>>> product(i<<1|1 for i in range(7,15))
45808142625
>>> _.bit_length()
36

I'll replace the patch.

--

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

Attached is a patch to improve the unit tests for the factorial function.

To compute the check value, it keeps a running total instead of recomputing the 
factorial from scratch inside the loop.  It checks up to range(999) and is 
quite fast.  The previous code checked range(10).

It also adds the following checks:
 * 0! == 1
 * (sys.maxsize+1)! => OverflowError
 * 10e100 => OverflowError

--
Added file: http://bugs.python.org/file17326/factorial-test.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


Added file: http://bugs.python.org/file17327/factorial-precompute-partials.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


Removed file: 
http://bugs.python.org/file17327/factorial-precompute-partials.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


Removed file: 
http://bugs.python.org/file17325/factorial-precompute-partials.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Changes by Alexander Belopolsky :


Added file: http://bugs.python.org/file17328/factorial-precompute-partials.patch

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

Daniel Stutzbach  added the comment:

Attached is a simple bash script to run math.factorial(n) through timeit for 
several values of n.  It makes comparing the speed of different builds MUCH 
easier.

--
Added file: http://bugs.python.org/file17329/factorial-speed.sh

___
Python tracker 

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

[issue8692] Use divide-and-conquer for faster factorials

[Alexander Belopolsky]

Alexander Belopolsky  added the comment:

Mark> Does anyone feel like doing a speed comparison between Daniel's C patch 
and a version with a direct no-frills iterative version of 
factorial_part_product (i.e., just a simple  'for (i = n; i <= m; i += 2) { 
 }?

Not a direct answer to your question, but replacing a bisect with a no-frills 
algorithm in my precompute patch gives the following timings:

   nbisect   no-frills
   100  38.9 us  38.5 us
  1000  .904 ms  1.08 ms
 1  35.4 ms  50.3 ms


The no-frills product still takes 20 lines of C code though:

n = last - first + 1;
if (n <= 0)
return PyLong_FromLong(1L);

result = PyLong_FromUnsignedLong(ODD(first));
if (result == NULL)
return NULL;
for  (i = 1; i < n; ++i) {
x = PyLong_FromUnsignedLong(ODD(first + i));
if (x == NULL)
goto error;
tmp = PyNumber_Multiply(result, x);
Py_DECREF(x);
if (tmp == NULL)
goto error;
Py_DECREF(result);
result = tmp;
}
return result;
 error:
Py_DECREF(result);
return NULL;

--

___
Python tracker 

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

[issue4898] {context, unified}_diff add spurious trailing whitespace if fromfiledate/tofiledate are emptyk

[R. David Murray]

Changes by R. David Murray :


--
resolution:  -> fixed
stage:  -> committed/rejected
status: open -> closed
superseder:  -> difflib should separate filename from timestamp with tab

___
Python tracker 

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

[issue8708] OpenID blunder

[Martin v . Löwis]

Martin v. Löwis  added the comment:

I have retired the user Jack.Diederich.

In the future, please use the meta tracker to discuss issues with this tracker.

--
nosy: +loewis -Jack.Diederich

___
Python tracker 

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

[issue8705] shutil.rmtree with empty filepath

[R. David Murray]

Changes by R. David Murray :


--
nosy: +tarek

___
Python tracker 

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

[issue8705] shutil.rmtree with empty filepath

[Ray.Allen]

Ray.Allen  added the comment:

Tested on Debian 5, also not occurs.

--
nosy: +ysj.ray

___
Python tracker 

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