Number: 591

Date: 10-Apr-84 11':16':06

Submitter: Sannella.PA

Source: JonL.pa

Subject: want opcode for FIXP, NUMBERP, LITATOM

Assigned To: 

Attn: Charnley, Herring, JonL, Purcell, vanMelle

Status: Open

In/By: 

Problem Type: Performance

Impact: Moderate

Difficulty: 

Frequency: Everytime

Priority: Perhaps

System: Language Support

Subsystem: Microcode

Machine: 

Disk: 

Lisp Version: 

Source Files: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Disposition: '
["masinter" "12-Sep-84 12':45':53" Attn': Status':(Wish->Open) Impact':(Annoying->Moderate) Description':]'
["JonL.pa" "23-Sep-84 22':23':59" Description':]

Description: '
[Currently, Larry and I are thinking of using some codes in the quantum map -- MDSTypeTable -- to indicate various classes and subclasses of datatypes; thus the type testing opcodes for FIXP, NUMBERP and several others would simply test for some union of bits being on in that map entry.  The particular "union of bits" would be stored in the alphabyte of the proposed typetesting opcode.  -- JonL  23-Sep-84 --]'
'
[lmm': I think the consensus is to do a type-predicate opcode with alpha-byte to allow new datatypes to think they are LITATOM/NUMBERP. I wonder if that''s a separate AR]'
'
'
Date':  2 APR 84 15':09 PST'
From': JONL.PA'
Subject': Re': Lisp': microcode enhancements'
To':   Masinter, LispSupport'
cc':   sheil, JONL, vanMelle, Charnley'
'
In response to the message sent  27 Mar 84 23':06 PST from Masinter.pa'
'
On the file [Phylum]<LispCore>Doc>Ucode.Suggestion is a note from me sent'
back in early January.  I proposed a new opcode that operates similarly'
to TYPEP except that its alphabyte would be a "high end of range" rather'
than an exact type to match.  So, discarding the typecode 0 (which my note'
fails to make clear) one would compile, say,  NUMBERP, in 2 bytes instead'
of the 12 or 13 it now takes.'
'
I also proposed using the TYPEP opcode for LITATOM; there is a discussion about'
the performance effects if TYPEP and LISTP share microcode.'
'
-----'
'
Date':  7 APR 84 23':34 PST'
From': MASINTER.PA'
Subject': AR, want opcode for FIXP, NUMBERP, LITATOM'
To':   LispSupport'
cc':   JonL'
'
I would agree with this proposal, with some modifications. '
'
First, there are some points which have a type table entry of 0. Thus, ILEQ is not reasonable, but 0<ntypx<alpha might be. However, given statistical frequency, a DISPATCH might be just as well, with 3 opcodes':'
'
FIXP, NUMBERP, LITATOM.'
'
Actually, we have proposed in the past a combination opcode which does the test and a conditional jump':'
'
JFIXP, JNFIXP, JNUMBERP, JNNUMBERP, JLITATOM, JNLITATOM.'
'
There is some (complex) logic in the compiler available already which will compile the unusual cases where the predicate is NOT used merely to determine a branch, or when a long branch is needed. '
'
I believe with the advent of BIGNUMs that we will absolutely want bignums to satisfy FIXP and NUMBERP, and that indeeed we will want rationals to be NUMBERP. Thus, there is another argument which says that the determination of these predicates should not be made by a numerical comparison of the type number, but rather by a bit test in the DTD, which would give us the opportunity to make odd sub-classes of these datatypes.'
'
[JonL': I''m cc':ing you for your comments; please feel free to add them to this AR. Since this is a Difficulty HARD requiring work on all three microcodes and the compiler, and an impact MINOR or MODERATE, and there are some open design issues, I think we should make sure we''ve resolved all of the open design questions before pressing ahead with implementation.]'
Date': 11 Jan 84 02':43 PST'
From': JonL.pa'
Subject': New suggestion. And cold data to douse hot conjecture'
To': Masinter'
cc': vanMelle, Charnley, Purcell, JonL, BLISP'
'
Re': your message of 6 JAN 84 17':12 PST'
'
Based on some observations while re-running a few of the dorado '
benchmarks, I suggest adding a new opcode which is like TYPEP, '
except that it checks for type number ILEQ rather than EQ to '
the data byte; reasoning follows below.'
'
Interestingly, while re-running these benchmarks, I uncovered'
several items which should put to rest the conjectures that '
LITATOM isn''t statistically important, and that adding a micro'
instruction to the TYPEP opcode would result in a net loss.  '
In the commentary below, "system" means SYSFILES on FULL.SYSOUT'
plus another dozen or so of my favorite <Lisp>Library> files.'
'
'
1) Masterscope shows 357 system callers of LITATOM -- almost'
   double the number of all the other TYPEP generators combined'
   (excepting one, which I''ll discuss in 2 below).  The others, '
   and their "weights", with some overlap, are STRINGP(112), '
   FLOATP(30), SMALLP(83), STACKP(20), and ARRAYP(40);  FIXP '
   doesn''t figure in here since it is a union of types, and '
   no place gives rise to a bare TYPEP(\FIXP) call.   If the '
   performance of LITATOM isn''t important, then maybe that of '
   the others isn''t either?'
'
   More to the point, if LITATOM were to use TYPEP, then     '
   *** regardless of whether the 100% to 200% speedup were'
   ever statisticaly observable *** the fact that two bytes'
   would be saved on each usage would free up at least a page'
   and a half of system space, and probably more.'
'
2) LISTP (opcode) generators are often "hidden", in that the'
   MAP series open-code using it, and many iterative statements'
   would also.  There must be thousands of places in the system'
   where LISTP is used.  So I decided to run some benchmarks to'
   see ** how much ** the extra microinstruction really cost.'
'
   Most of Gabriel''s "list intensive" benchmarks don''t even '
   generate any usages of TYPEP (or LISTP) -- many use ATOM'
   which generates NTYPX;  but BOYER does (via NLISTP) -- and  '
   it calls EQUAL which also does -- all in central rather '
   than in peripheral parts of the program.  So I ran BOYER 6  '
   times in each flavor of microcode, and came up with a '
'
   ***** 0%  difference *****'
'
   Actual data, hand-recorded in my lab notebook are also'
   reproduced below.  For a second set of comparisons, I'
   put the file <Lisp>Library>BSEARCH on my local disk, and'
   did 5 runs of (LOAD ''{DSK}BSEARCH ''PROP), and then 3 runs of'
   (MAKEFILE ''{DSK}BSEARCH ''NEW)in each flavor of microcode.'
   The result?'
'
   ***** 0%  difference *****'
'
   These results sound so incredible, that I just had to run'
   *something* that would show the difference.  A tightest-'
   possible loop, cdring down a length-1000 list 10,000 times,'
   indeed showed the differential':  without the extra micro-'
   instruction, it was 2815.5 nanoseconds per loop, and with'
   the extra one, it was 2879.3 nanoseconds; happily, this'
   difference is effectively 64 nanoseconds (which, by the'
   way, is only a 2% difference -- practically, the largest '
   measurable for this change).'
'
'
Of course, this "0%" is a statistical figure, which just '
means that any differences were below the "noise" in measuring.'
Still, one could hardly have a more clear-cut decision about'
the advisibility of supporting LITATOM with the TYPEP opcode.'
If one is still uncertain, then the implementation of the'
LISTP opcode could be differentiated from that of the TYPEP '
opcode (maybe they are already on the other machines?? it just '
happened to be convenient on the Dorado for them to be exactly '
the same micro routine).'
'
'
A final comment.  Until now, I didn''t really realize how'
badly FIXP compiles -- 9 bytes instead of 1 or 2.  NUMBERP is'
even worse!   Masterscope reports 195 direct system callers of'
FIXP, 136 of NUMBERP, and 73 of ATOM (there are probably more,'
and there''s almost no overlap).  If we had a new 2-byte opcode'
which was like TYPEP, but it checked for ILEQ rather than EQ of'
the type code, then all of these functions could use it, and '
all would benefit enormously.'
    (FIXP X)    == (ILEQ (NTYPX X) 2)'
    (NUMBERP X) == (ILEQ (NTYPX X) 3)'
    (ATOM X)    == (ILEQ (NTYPX X) 4)'
[a swap of LISTP and STRING typecodes would also permit strings'
to be considered "atoms"]'
'
'
---------------------------------------------------------------'
  Data': Times in seconds. Format <GC>/<CPU> where both needed '
---------------------------------------------------------------'
'
'
BOYER':    Vanilla ucode | Crusty ucode'
------------------------|----------------'
            13.4/17.6   |  13.4 17.7'
            13.3/17.8   |  13.4/17.9'
            13.4/17.9   |  13.5/17.9'
            13.4/17.8   |  13.4/17.9'
            13.2/17.5   |  13.3/17.7'
            13.4/17.8   |  13.4/17.9'
'
[on LOAD, the last 3 runs only are reported, since the early'
runs tended to be obscured by swapping, page initialization,'
etc.  The times "stabilized" after that.]'
LOAD':     Vanilla ucode | Crusty ucode    '
------------------------|----------------    '
             1.04       |    1.04'
             1.04       |    1.04'
             1.04       |    1.03       [Bizarre, no?]'
'
MAKEFILE': Vanilla ucode | Crusty ucode  '
------------------------|----------------    '
            7.17        |    7.17'
            7.17        |    7.17'
            7.18        |    7.18'
'


Workaround: 

Test Case: 

Edit-By: JonL.pa

Edit-Date: 23-Sep-84 22':23':59