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

Discussion of Common Lisp

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

Postby wvxvw » Thu Nov 01, 2012 2:00 pm

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.
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

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

Postby sylwester » Thu Nov 01, 2012 3:23 pm

I don't think multiple value return cons at all. It's most likely implemented in stack frame just like arguments are.
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p
sylwester
 
Posts: 83
Joined: Mon Jul 11, 2011 2:53 pm

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

Postby wvxvw » Thu Nov 01, 2012 11:35 pm

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?
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

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

Postby edgar-rft » Fri Nov 02, 2012 12:16 am

wvxvw wrote:...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
edgar-rft
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby wvxvw » Fri Nov 02, 2012 1:45 am

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 :/
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

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

Postby edgar-rft » Fri Nov 02, 2012 2:28 am

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
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby edgar-rft » Fri Nov 02, 2012 3:18 am

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
edgar-rft
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby wvxvw » Fri Nov 02, 2012 4:05 am

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?
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

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

Postby edgar-rft » Fri Nov 02, 2012 6:44 am

"wxvxw wrote: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.

"wxvxw wrote: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
edgar-rft
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby wvxvw » Fri Nov 02, 2012 7:01 am

Oh, integers of course. OK, I had dim memories there was something like that in this book... time to look into it again. Thanks! :)
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 2 guests

cron