A way to convert a float to integer w/o impact on memory?

[wvxvw]

I've looked into all rounding / truncating / flooring functions that I know, but all of them return multiple values, and, as an artefact, even if the second value isn't used, they create and immediately dispose of new conses. This later causes GC to kick in and can slow down the execution at random spots at seemingly random fashion.
So, is there a way to avoid doing (floor x y) w/o consing extra memory? Even if there's an SBCL-specific way, that's good too.

Code: Select all

(defun next-power-two-log (x)
  (declare (optimize (debug 0) (safety 0) (space 0) (speed 3)))
  (declare (type fixnum x))
  (ash 1 (1+ (the signed-byte (floor (the single-float (log x 2)))))))

Here's an example of what I was trying to do, but it doesn't work because the type hint of signed-byte is ignored. But this is only to illustrate that even with speed 3, the second (and obviously redundant) value from floor is created and discarded.

[sylwester]

I don't think multiple value return cons at all. It's most likely implemented in stack frame just like arguments are.

[wvxvw]

Hm... after some thought... how many bits is a fixnum on a 64 bit system? I think this must have been a problem then. In my test no value is larger then 2^31, but what if they can't be even this big and it creates long integers?

[edgar-rft]

...how many bits is a fixnum on a 64 bit system?

The number of bits is implementation-dependent, usually two or three bits less than the CPU register width:

Code: Select all

CL-USER> (integer-length most-positive-fixnum)
62
CL-USER> (integer-length most-negative-fixnum)
62

Both should give the same number of bits. The results above are from SBCL 1.1.0 on Linux debian-64 2.6.32-5-amd64.

- edgar

[wvxvw]

Below is my complete test:

Code: Select all

(defun next-power-two-loop (x)
  (declare (optimize (debug 0) (safety 0) (space 0) (speed 3)))
  (declare (type fixnum x))
  (if (and (> x 0) (= (logand x (1- x)) 0))
      x
      (loop with result fixnum = 1
            do (setq result (ash result 1))
            do (when (> result x) (return result)))))

(defun next-power-two-log (x)
  (declare (optimize (debug 0) (safety 0) (space 0) (speed 3)))
  (declare (type fixnum x))
  (ash 1 (the fixnum
           (+ 1
              (the fixnum (sb-kernel:%unary-truncate/single-float
                           (the single-float (log x 2))))))))

(let ((ints (mapcar #'random (make-list 100000 :initial-element (ash 1 31)))))
  (gc)
  (time (dolist (i ints) (next-power-two-loop i)))
  (gc)
  (time (dolist (i ints) (next-power-two-log i))))


You can see that it prints the information about the "bytes consed" for next-power-two-log. I cannot really understand where it is coming from :/

[edgar-rft]

It's probably the LOG function. This gives me exactly the same number of consed bytes:

Code: Select all

(defun log2 (x)
  (declare (optimize (debug 0) (safety 0) (space 0) (speed 3)))
  (declare (type fixnum x))
  (log x 2))

SBCL provides SB-KERNEL::LOG2, which conses only approx. half the number of bytes, but still many.

- edgar

[edgar-rft]

Code: Select all

(defun next-power-two (x)
  (if (< x 1)
      (error "no positive integer: ~s" x)
      (ash 1 (integer-length x))))

Test result: 0 bytes consed (may be different in other implementations than SBCL).

- edgar

[wvxvw]

Thanks for the last version. That wasn't a serious test, actually there are many non-trivial ways to round up to the closest power of two fast (or, perhaps even faster then your suggestion).
I realize now that floor is not the culprit, but why would log cons any memory? Is this something that is inherent to this algorithm? Do you know of any good articles on how to do logarithm by hand?

[edgar-rft]

Why would log cons any memory?

Because Common Lisp's LOG accepts all types of numerical arguments (except zero), and with negative input LOG is even capable to return complex numbers. All-in-all this is a bit more complicated than just computing a simple binary integer logarithm. I'm afraid that LOG is already "too big" for such a simple problem and tries to solve the computation in an unneccessarily complicated way. That's the drawback of a programming language handling data types automatically. Common Lisp is good, but not perfect.

Do you know of any good articles on how to do logarithm by hand?

On what type of numbers? Bytes, integers, fractions, floats, complexes? Every type needs a different algorithm if the result shall be fast.

In case of doubt:

Donald E. Knuth, "The Art of Computer Programming", Volume 1 "Fundamental Algorithms", Chapter 1.2.2 "Numbers, Powers, and Logarithms"

- edgar

[wvxvw]

Oh, integers of course. OK, I had dim memories there was something like that in this book... time to look into it again. Thanks!