News for hackers. Stuff that matters.
Re:How to Print Integers Really Fast by im3w1l on Sunday December 24, 2017 @12:43AM (#15998177)
A fairly common special case of printing integers is printing all integers from 0 to N. In that case you can use a trick: Keep a string representation of the current number and increment the string representation.
Re:How to Print Integers Really Fast by userbinator on Sunday December 24, 2017 @02:14AM (#15998423)
Anyone who has played the old arcade games with fixed-width score counters will have seen this trick in action --- many of those ran on 8-bit processors without multiply or divide instructions, so it was much easier to keep the score as an array of digits and increment those than a binary variable and the equivalent of an itoa() every time it needed to be displayed.

More succinctly, in pseudocode:

    while(++digits[i] > '9')
        digits[i--] = '0';
By starting the increment at the non-rightmost digit, it also allows for easy addition of powers of 10: 10, 100, 1000, etc.
Re:How to Print Integers Really Fast by mikebenfield on Sunday December 24, 2017 @03:22AM (#15998604)
Related to this is binary coded decimal [1]: let each nibble (4 bits) of your integer represent a decimal digit 0-9. Then do your arithmetic in binary, but after each operation run a special CPU instruction to "correct" the result to what it should be in decimal.

[1] https://en.wikipedia.org/wiki/Binary-coded_decimal

Re:How to Print Integers Really Fast by im3w1l on Sunday December 24, 2017 @04:17AM (#15998743)
There are two BCD formats. Packed (what you describe) and unpacked (where only a single digit is stored per byte). Unpacked seems to have the advantage that converting to ASCII is just a matter of setting two bits, and converting from ASCII is just a matter of masking those out.

I found this example very illuminating

    sub    AH,AH    ; clear AH
    mov    AL,'6'   ; AL := 36H
    add    AL,'7'   ; AL := 36H+37H = 6DH
    aaa             ; AX := 0103H
    or     AL,30H   ; AL := 33H
because aaa instruction clears the high nibble of AL, it works with either unpacked BCD or with ASCII (but always outputs BCD).

http://service.scs.carleton.ca/sivarama/asm_book_web/Instruc... (page 8)

But iiuc aaa didn't make it in the transation to 64bit processors.

Re:How to Print Integers Really Fast by s_gourichon on Sunday December 24, 2017 @11:48AM (#16000207)
Some CPUs like the Saturn from Hewlett-Packard [1] are designed for BCD. Though they can perform binary operations, registers are structured for 64-bit floating point operations with a 4-bit wide bus and nibble-granularity addressing of register nibbles: 1 sign, 12 mantissa, 3 exponent.

[1] https://en.wikipedia.org/wiki/HP_Saturn

Re:How to Print Integers Really Fast by simias on Sunday December 24, 2017 @09:35AM (#15999687)
The Game Boy CPU kept track of nibble overflows and had an instruction called DAA to adjust the packed BCD value in the A register after an arithmetic operation. If you disable this instruction in an emulator many games start counting your score in hexadecimal (Tetris even has the sprites A to F interestingly, so you actually get your full score displayed correctly).
Re:How to Print Integers Really Fast by s_gourichon on Sunday December 24, 2017 @11:42AM (#16000180)
The Game Boy "had" this DAA instruction from its CPU, a variant of the Z80. This trick may well have been used also on some Amstrad CPC games also, then.

Indeed, the Z80 itself, which people like us know because it was very common in 8bit home computers, is an enhancement of the Intel 8080, which itself is an ancestor of the current Intel CPUs.

Incidentally, Z80 CPUs are still manufactured 40+ years later ( https://en.wikipedia.org/wiki/Zilog_Z80 ) and benefit from modern C compilers like SDCC and software development environments like z88dk or the one I wrote for the Amstrad CPC: https://github.com/cpcitor/cpc-dev-tool-chain (written for Linux and tools like GNU make, wget, etc).

That said, writing C code that compiles to packed BCD and the use of DAA at assembly level does not seem very practical. If few numbers are manipulated, unpacked BCD is simpler (closer to string, less code to handle) both in assembly and in C.

Re:How to Print Integers Really Fast by pixelbeat on Sunday December 24, 2017 @08:58AM (#15999528)
GNU seq uses this trick:

slow path:

    seq -f '%.1f' inf | pv > /dev/null
     ...[  12MiB/s]
fast path:

    seq inf | pv > /dev/null
     ...[ 491MiB/s]
Re:How to Print Integers Really Fast by zbentley on Sunday December 24, 2017 @12:01PM (#16000262)
Can you explain that a bit more? I know "seq", but am unsure what your examples are illustrating. Thanks!
Re:How to Print Integers Really Fast by taejo on Sunday December 24, 2017 @12:45PM (#16000436)
-f specifies a format, so it can't use the specialized itoa implementation, but probably just uses printf.
Re:How to Print Integers Really Fast by blt on Sunday December 24, 2017 @01:03AM (#15998228)
This is a common case? Besides educational exercises, why? I would have guessed most printed integers are random ID numbers, prices, database foreign keys, etc.
Re:How to Print Integers Really Fast by MaulingMonkey on Sunday December 24, 2017 @01:21AM (#15998289)
> This is a common case? Besides educational exercises, why?

Sequential IDs permeate everything. Array indicies. Memory offsets. Line numbers, track numbers, page numbers, check numbers... the dates of your daily logs, your calendars... heck, enumeration attacks can be as simple as "what happens when I increment this number by exactly 1 when making this GET request?"

Re:How to Print Integers Really Fast by jzwinck on Sunday December 24, 2017 @01:14AM (#15998264)
Line numbers in less(1) or GitHub. Row numbers in Excel, Pandas, R, etc.

The most common way to label rows is with sequential numbers.

Re:How to Print Integers Really Fast by eesmith on Sunday December 24, 2017 @03:07AM (#15998558)
FWIW, in a file with 1,000,000 lines, the best-of-3 time for "less filename > /dev/null" is:

  2.508u 0.152s 0:02.66 99.6%	0+0k 0+0io 0pf+0w
and the best-of-3 time for "less -N filename > /dev/null" is:

  2.568u 0.159s 0:02.73 99.2%	0+0k 0+0io 0pf+0w
That is, it doesn't seem like printing sequential is the limiting factor in performance.

This is with "less 458", "Copyright (C) 1984-2012". I downloaded and compiled stock 487 and the best-of-3 times went up to 0:02.94 for both cases.

Checking the source code, it does not appear to use knowledge of the previous output index in order to save time. The relevant code is:

        static int
  iprint_linenum(num)
        LINENUM num;
  {
        char buf[INT_STRLEN_BOUND(num)];

        linenumtoa(num, buf);
        putstr(buf);
        return ((int) strlen(buf));
  }
where

  #define TYPE_TO_A_FUNC(funcname, type) \
  void funcname(num, buf) \
          type num; \
          char *buf; \
  { \
          int neg = (num < 0); \
          char tbuf[INT_STRLEN_BOUND(num)+2]; \
          register char *s = tbuf + sizeof(tbuf); \
          if (neg) num = -num; \
          *--s = '\0'; \
          do { \
                  *--s = (num % 10) + '0'; \
          } while ((num /= 10) != 0); \
          if (neg) *--s = '-'; \
          strcpy(buf, s); \
  }
  
  TYPE_TO_A_FUNC(linenumtoa, LINENUM)
Re:How to Print Integers Really Fast by blt on Sunday December 24, 2017 @01:32PM (#16000625)
hmm, maybe someone can get a pull request for implementing this optimization :)
Re:How to Print Integers Really Fast by eesmith on Sunday December 24, 2017 @08:28PM (#16002189)
While I know you meant that comment in jest, it suggests that I wasn't clear enough.

My implicit argument is that there's there's no reason to believe that line counting adds anything more than trivial overhead to the less output, so there's no reason to even consider this optimization, much less getting to the point to make a pull request.

Re:How to Print Integers Really Fast by eternauta3k on Sunday December 24, 2017 @06:24AM (#15999078)
This is so common that there are dedicated ICs to count in base 10.