Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: The 10**21 Problem (Part 4)

by RMGir (Prior)
on May 19, 2014 at 16:33 UTC ( [id://1086693]=note: print w/replies, xml ) Need Help??


in reply to The 10**21 Problem (Part 4)

I'm afraid you didn't pick a very stable "magic function" to optimize for.

It doesn't work with the first Python 2.x I tested it on (which turns out to be 2.7.2):

$ python Python 2.7.2 (default, Oct 27 2011, 17:53:49) [GCC 4.3.2] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> /bb/build/Linux-x86_64-32/release/robolibs/big2014.21-611907-20140 +519105223/lib/dpkgroot KeyboardInterrupt >>> magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+c +hr(103)+chr(125)+chr(48) >>> for r in ["M", "D", "C", "L", "X", "V", "I"]: ... n = hash(r + magic) % 1001 ... print r, n ... M 338 D 602 C 93 L 733 X 555 V 933 I 402
It fails the same way with Python 2.6.7 on my Mac, but succeeds with Python 2.5.6:
$ python2.5 Python 2.5.6 (r256:88840, Oct 11 2012, 20:14:10) [GCC 4.2.1 Compatible Apple Clang 4.0 (tags/Apple/clang-418.0.60)] on +darwin Type "help", "copyright", "credits" or "license" for more information. >>> magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+c +hr(103)+chr(125)+chr(48) >>> for r in ["M", "D", "C", "L", "X", "V", "I"]: ... n = hash(r + magic) % 1001 ... print r, n ... M 1000 D 500 C 100 L 50 X 10 V 5 I 1

Mike

Replies are listed 'Best First'.
Re^2: The 10**21 Problem (Part 4)
by eyepopslikeamosquito (Archbishop) on May 19, 2014 at 22:04 UTC

    Luckily, it was accepted by both shinh's golf server, when I submitted it about a month ago, and the code golf server also (currently down). Shinh's server runs Python 2.7.2 on Linux, the code golf server Python 2.5 on Linux.

    It would be interesting to see the actual hash value and Python version by running this version:

    import sys print sys.version_info magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+chr(1 +03)+chr(125)+chr(48) for r in ["M", "D", "C", "L", "X", "V", "I"]: h = hash(r + magic) n = h % 1001 print r, n, "(" + str(h) + ")"
    which produced for me on Windows just now:
    sys.version_info(major=2, minor=7, micro=5, releaselevel='final', seri +al=0) M 1000 (2094745652) D 500 (1641493353) C 100 (277891714) L 50 (1566900385) X 10 (1666291637) V 5 (-1570643069) I 1 (1060402344)
    Strange, that this is the same Python version 2.7.5 as reported by mr_mischief but on a different platform (Windows vs MacOS). I tested both 32-bit and 64-bit Python on Windows (multiple versions) and didn't see a failure.

    On shinh's golf server it produced:

    sys.version_info(major=2, minor=7, micro=2, releaselevel='final', seri +al=0)\n M 1000 (2094745652) D 500 (1641493353) C 100 (277891714) L 50 (1566900385) X 10 (1666291637) V 5 (-1570643069) I 1 (1060402344)
    This is doubly strange because that is the same Python version 2.7.2 running on the same platform, Linux, which failed for RMGir!

    I will check the Python C sources version history later when I get more time.

      Very strange.

      I even checked to make sure bitness had no impact by running both the 32 and 64-bit versions of the python on my mac, but both give the same result.

      I was doing that wrong. Running a 32-bit version of python (by following these directions) on my mac, I get the answer you expect.

      So I suspect it's just that the python hash function works for your approach in 32-bit builds, but not in 64.


      Mike

        Yes, I believe you are correct.

        From stringobject.c:

        static long string_hash(PyStringObject *a) { register Py_ssize_t len; register unsigned char *p; register long x; if (a->ob_shash != -1) return a->ob_shash; len = Py_SIZE(a); p = (unsigned char *) a->ob_sval; x = *p << 7; while (--len >= 0) x = (1000003*x) ^ *p++; x ^= Py_SIZE(a); if (x == -1) x = -2; a->ob_shash = x; return x; }
        we can see that it is not whether the platform itself is 64-bit that matters, but whether the long type used by the C compiler that Python was built with is 64-bit. For Python built with a 32-bit long my solution should work, for a 64-bit long it will not.

        On 64-bit architectures, Windows C compilers tend to use the LLP64 programming model (32-bit long), while most others tend to use the LP64 model (64-bit long). From this stack overflow question:

        The true "war" was for sizeof(long), where Microsoft decided for sizeof(long) == 4 (LLP64) while nearly everyone else decided for sizeof(long) == 8 (LP64). Note that a programming model is a choice made on a per-compiler basis, and several can coexist on the same OS. However, the programming model chosen as the primary model for the OS API typically dominates.

        Hmmm, I see from this later stringobject.c that _Py_HashSecret_* has been added, presumably to protect against DoS attacks that exploit hash collisions in Python dictionaries.

        static long string_hash(PyStringObject *a) { register Py_ssize_t len; register unsigned char *p; register long x; #ifdef Py_DEBUG assert(_Py_HashSecret_Initialized); #endif if (a->ob_shash != -1) return a->ob_shash; len = Py_SIZE(a); /* We make the hash of the empty string be 0, rather than using (prefix ^ suffix), since this slightly obfuscates the hash secre +t */ if (len == 0) { a->ob_shash = 0; return 0; } p = (unsigned char *) a->ob_sval; x = _Py_HashSecret.prefix; x ^= *p << 7; while (--len >= 0) x = (1000003*x) ^ *p++; x ^= Py_SIZE(a); x ^= _Py_HashSecret.suffix; if (x == -1) x = -2; a->ob_shash = x; return x; }

        See also:

Re^2: The 10**21 Problem (Part 4)
by mr_mischief (Monsignor) on May 19, 2014 at 20:15 UTC

    I get the same failure under 2.7.5 on Mac and 2.6.6 on CentOS as well.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1086693]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (7)
As of 2024-03-19 11:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found