RE: One more dict trick

Another version of the patch attached, a bit faster and with a large new
comment block explaining it.  It's looking good!  As I hope the new comments
make clear, nothing about this approach is "a mystery" -- there are
explainable reasons for each fiddly bit.  This gives me more confidence in
it than in the previous approach, and, indeed, it turned out that when I
*thought* "hmm! I bet this change would be a little faster!", it actually
was <wink>.

Index: Objects/dictobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v
retrieving revision 2.96
diff -c -r2.96 dictobject.c
*** Objects/dictobject.c	2001/05/27 07:39:22	2.96
--- Objects/dictobject.c	2001/06/01 00:17:07
***************
*** 12,123 ****
   */
  #define MINSIZE 8

! /* define this out if you don't want conversion statistics on exit */
  #undef SHOW_CONVERSION_COUNTS

  /*
! Table of irreducible polynomials to efficiently cycle through
! GF(2^n)-{0}, 2<=n<=30.  A table size is always a power of 2.
! For a table size of 2**i, the polys entry is 2**i + j for some j in 1 thru
! 2**i-1 inclusive.  The polys[] entries here happen to add in the smallest j
! values "that work".  Work means this:  given any integer k in 1 thru 2**i-1

RE: One more dict trick

Heh.  I was implementing 128-bit floats in software, for Cray, in about
1980.  They didn't do it because they *wanted* to make the Cray boxes look
like pigs <wink>.  A 128-bit float type is simply necessary for some
scientific work:  not all problems are well-conditioned, and the "extra"
bits can vanish fast.  Went thru the same bit at KSR.  Just yesterday Konrad
Hinsen was worrying on c.l.py that his scripts that took 2 hours using
native floats zoomed to 5 days when he started using GMP's
arbitrary-precision float type *just* to get 100 bits of precision.

When KSR died, the KSR-3 on the drawing board had 128-bit registers.  I was
never quite sure why the founders thought that would be a killer selling
point, but it wasn't for floats.  Down in the trenches we thought it would
be mondo cool to have an address space so large that for the rest of our
lives we'd never need to bother calling free() again <0.8 wink>.

RE: One more dict trick

[Thomas Wouters]
> Why ? Bumping register size doesn't mean Intel expects to use it all as
> address space. They could be used for video-processing,

Bingo.  Common wisdom holds that vector machines are dead, but the truth is
virtually *everyone* runs on a vector box now:  Intel just renamed "vector"
to "multimedia" (or AMD to "3D Now!"), and adopted a feeble (but
ever-growing) subset of traditional vector machines' instruction sets.

> or to represent a modest range of rationals <wink>, or to help core
> 'net routers deal with those nasty IPv6 addresses.

KSR's founders had in mind bit-level addressability of networks of machines
spanning the globe.  Were he to press the point, though, I'd have to agree
with Eric that they didn't really *need* 128 bits for that modest goal.

> I'm sure cryptomunchers would like bigger registers as well.

Agencies we can't talk about would like them as big as they can get them.
Each vector register in a Cray box actually consisted of 64 64-bit words, or
4K bits per register.  Some "special" models were constructed where the
vector FPU was thrown away and additional bit-fiddling units added in its
place:  they really treated the vector registers as giant bitstrings, and
didn't want to burn 64 clock cycles just to do, e.g., "one" conceptual xor.

> Oh wait... I get it! You were trying to get yourself in the
> historybooks as the guy that said "64 bits ought to be enough for
> everyone" 

That would be foolish indeed!  128, though, now *that's* surely enough for

RE: One more dict trick

Tim Peters writes:
 > When KSR died, the KSR-3 on the drawing board had 128-bit registers.  I was
 > never quite sure why the founders thought that would be a killer selling
 > point, but it wasn't for floats.  Down in the trenches we thought it would
 > be mondo cool to have an address space so large that for the rest of our
 > lives we'd never need to bother calling free() again <0.8 wink>.

  And given what (little) I know about the memory architecture on
those things, that actually would have be quite reasonable on that
platform!

  -Fred

--

-- 
Fred L. Drake, Jr.  <fdrake at acm.org>
PythonLabs at Digital Creations

FW: CP4E and Python newbies, it works!

Good for the soul!

-----Original Message-----
From: python-list-admin <at> python.org
[mailto:python-list-admin <at> python.org]On Behalf Of Ron Stephens
 [mailto:rdsteph <at> earthlink.net]
Sent: Thursday, May 31, 2001 7:12 PM
To: python-list <at> python.org
Subject: CP4E and Python newbies, it works!

I am a complete newbie, and with a very low programming IQ. Although I
had programmed a little in college thirty years ago, in Basic, PL/1 and
a very little assembler, and fooled around in later years on PC's at
home with Basic, then tried PERL, then an effort at Java, they were all
too much trouble to really use to program, given that it was a *hobby*
that was supposed to be fun. After all, I have a demanding day job that
has nothing to do with software, that requires extensive travel, and
four kids, a wife, two dogs, and a cat. Java et al, by the time I had
digested a couple of books and put in a lot of hours, was just no fun at
all to program; and I had to look in the book every other line of code
just to recall the syntax etc.; I could not keep it in my head.

Now, four months into Python, after being attracted by reading a blurb
about Guido van Rossum's Computer Programming for Everybody project, I
am in awe of his achievement. I am having fun; and if I can do so then
almost anyone can. I am really absent minded, lazy,  and not good at
detail. Yet I have done the following in four months, and I believe
Python therefore has  the potential to open up programming to a much
wider audience for a lot of people, which is nice:

Re: One more dict trick

Tim Peters <tim.one <at> home.com>:
>                      A 128-bit float type is simply necessary for some
> scientific work:  not all problems are well-conditioned, and the "extra"
> bits can vanish fast. 

Makes me wonder how competent your customers' numerical analysts were.
Where the heck did they think they were getting data with that many
digits of accuracy?  (Note that I didn't say "precision"...)
--

-- 
		<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Strict gun laws are about as effective as strict drug laws...It pains
me to say this, but the NRA seems to be right: The cities and states
that have the toughest gun laws have the most murder and mayhem.
        -- Mike Royko, Chicago Tribune

Re: One more dict trick

Tim Peters <tim.one <at> home.com>:
> Agencies we can't talk about would like them as big as they can get them.
> Each vector register in a Cray box actually consisted of 64 64-bit words, or
> 4K bits per register.  Some "special" models were constructed where the
> vector FPU was thrown away and additional bit-fiddling units added in its
> place:  they really treated the vector registers as giant bitstrings, and
> didn't want to burn 64 clock cycles just to do, e.g., "one" conceptual xor.

You've got a point...but I don't think it's really economical to build that
kind of hardware into general-purpose processors.  You end up with a camel.
You know, a horse designed by committee?
--

-- 
		<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

To make inexpensive guns impossible to get is to say that you're
putting a money test on getting a gun.  It's racism in its worst form.
        -- Roy Innis, president of the Congress of Racial Equality (CORE), 1988

RE: One more dict trick

[Tim]
> A 128-bit float type is simply necessary for some scientific work:  not
> all problems are well-conditioned, and the "extra" bits can vanish fast.

[ESR]
> Makes me wonder how competent your customers' numerical analysts were.
> Where the heck did they think they were getting data with that many
> digits of accuracy?  (Note that I didn't say "precision"...)

Not all scientific work consists of predicting the weather with inputs known
to half a digit on a calm day <wink>.  Knuth gives examples of
ill-conditioned problems where resorting to unbounded rationals is faster
than any known stable f.p. approach (stuck with limited precision) -- think,
e.g., chaotic systems here, which includes parts of many hydrodynamics
problems in real life.

Some scientific work involves modeling ab initio across trillions of
computations (and on a Cray box in particular, where addition didn't even
bother to round, nor multiplication bother to compute the full product tree,
the error bounds per operation were much worse than in a 754 world).

You shouldn't overlook either that algorithms often needed massive rewriting
to exploit vector and parallel architectures, and in a world where a
supremely competent numerical analysis can take a month to verify the
numerical robustness of a new algorithm covering two pages of Fortran, a
million lines of massively reworked seat-of-the-pants modeling code couldn't
be trusted at all without running it under many conditions in at least two
precisions (it only takes one surprise catastrophic cancellation to destroy
everything).

RE: One more dict trick

[EAR]
> You've got a point...

Well, really, they do -- but they had a much more compelling point when the
Cold War came with an unlimited budget.

> but I don't think it's really economical to build that kind of
> hardware into general-purpose processors.

Economical?  The marginal cost of adding even nutso new features in silicon
now for mass-market chips is pretty close to zero.  Indeed, if you're in the
speech recog or 3D imaging games (i.e., things that still tax a PC), Intel
comes around *begging* for new ideas to use up all their chip real estate.
The only one I recall them turning down was a request from Dragon's founder
to add an instruction that, given x and y, returned log(exp(x)+exp(y)).
They were skeptical, and turned out even *we* didn't need it <wink>.

> You end up with a camel.  You know, a horse designed by committee?

Yup!  But that's the camel Intel rides to the bank, so it will probably grow
more humps, on which to hang more bags of gold.

Re: One more dict trick

Tim Peters <tim.one <at> home.com>:
> Not all scientific work consists of predicting the weather with inputs known
> to half a digit on a calm day <wink>.  Knuth gives examples of
> ill-conditioned problems where resorting to unbounded rationals is faster
> than any known stable f.p. approach (stuck with limited precision) -- think,
> e.g., chaotic systems here, which includes parts of many hydrodynamics
> problems in real life.

Hmmm...good answer.  I still believe it's the case that real-world
measurements max out below 48 bits or so of precision because the real
world is a noisy, fuzzy place.  But I can see that most of the
algorithms for partial differential equationss would multiply those by
very small or very large quantities repeatedly.  The range-doubling
trick for catching divergences is neat, too.

So maybe there's a market for 128-bit floats after all.  I'm still
skeptical about how likely those applications are to influence the
architecture of general-purpose processors.  I saw a study once that
said heavy-duty scientific floating point only accounts for about 2%
of the computing market -- and I think it's significant that MMX
instructions and so forth entered the Intel line to support *games*,
not Navier-Stokes calculations.

That 2% will have to get a lot bigger before I can see Intel doubling
its word size again.  It's not just the processor design; the word size
has huge implications for buses, memory controllers, and the whole
system architecture.
--

-- 
		<a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>