3 ms·
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 cu
by im3w1l 9y ago
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.
- blt 9y agoThis is a common case? Besides educational exercises, why? I would have guessed most printed integers are random ID numbers, prices, database foreign keys, etc.
- jzwinck 9y agoLine numbers in less(1) or GitHub. Row numbers in Excel, Pandas, R, etc. The most common way to label rows is with sequential numbers.
- eesmith 9y agoFWIW, 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)
- blt 9y agohmm, maybe someone can get a pull request for implementing this optimization :)
- eesmith 9y agoWhile 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.
- MaulingMonkey 9y ago> 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?"
- eternauta3k 9y agoThis is so common that there are dedicated ICs to count in base 10.
- userbinator 9y agoAnyone 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.
- mikebenfield 9y agoRelated 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 https://en.wikipedia.org/wiki/Binary-coded_decimal
- im3w1l 9y agoThere 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/Instructor_copies/ch11_bcd.pdf 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.
- simias 9y agoThe 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).
- pixelbeat 9y agoGNU seq uses this trick: slow path: seq -f '%.1f' inf | pv > /dev/null ...[ 12MiB/s] fast path: seq inf | pv > /dev/null ...[ 491MiB/s]