headers
Vijay Mathew | 11 Jun 2011 03:05
Picon
Gravatar

Socket reuse-address problem

The call to sockopt-reuse-address seems to have no effect.

(setf socket (make-instance 'sb-bsd-sockets:inet-socket
                            :type type :protocol protocol)
(setf (sb-bsd-sockets:sockopt-reuse-address socket) t)
(setf (sb-bsd-sockets:non-blocking-mode socket) t)
(sb-bsd-sockets:socket-bind socket ip port)
(sb-bsd-sockets:socket-listen socket backlog)
Attempt to rebind to the same port raises the following error:

Socket error in "bind": EADDRINUSE (Address already in use)
   [Condition of type SB-BSD-SOCKETS:ADDRESS-IN-USE-ERROR]
What am I doing wrong?

Thank you,

--Vijay

------------------------------------------------------------------------------
EditLive Enterprise is the world's most technically advanced content
authoring tool. Experience the power of Track Changes, Inline Image
Editing and ensure content is compliant with Accessibility Checking.
http://p.sf.net/sfu/ephox-dev2dev
Permalink | Reply | 1 comment |
headers
Nikodemus Siivola | 11 Jun 2011 14:13
Gravatar

Re: Socket reuse-address problem

On 11 June 2011 04:05, Vijay Mathew <vijay.the.schemer <at> gmail.com> wrote:
> The call to sockopt-reuse-address seems to have no effect.
>
> (setf socket (make-instance 'sb-bsd-sockets:inet-socket
>                            :type type :protocol protocol)
> (setf (sb-bsd-sockets:sockopt-reuse-address socket) t)
> (setf (sb-bsd-sockets:non-blocking-mode socket) t)
> (sb-bsd-sockets:socket-bind socket ip port)
> (sb-bsd-sockets:socket-listen socket backlog)
> Attempt to rebind to the same port raises the following error:
>
> Socket error in "bind": EADDRINUSE (Address already in use)
>   [Condition of type SB-BSD-SOCKETS:ADDRESS-IN-USE-ERROR]
> What am I doing wrong?

See: http://www.unixguide.net/network/socketfaq/4.5.shtml

Perhaps you're looking for SO_REUSEPORT? (Which, embarrassingly,
SB-BSD-SOCKETS doesn't appear to support right now.)

Cheers,

 -- nikodemus

------------------------------------------------------------------------------
EditLive Enterprise is the world's most technically advanced content
authoring tool. Experience the power of Track Changes, Inline Image
Editing and ensure content is compliant with Accessibility Checking.
http://p.sf.net/sfu/ephox-dev2dev
_______________________________________________
(Continue reading)

Permalink | Reply | 0 comments |
headers
Cheung, Matthew G | 14 Jun 2011 01:13

modular arithmetic

I was wondering if sbcl does any optimisations when performing modular arithmetic.  I have written some
code that does elliptic curve operations and I was trying to see if I could improve performance by
implementing any of the algorithms designed to improve performance of modular operations such as fast
reductions for NIST primes.  What I have written appears to be correct since it agrees with the built in mod
operator, but it actually takes longer.  Is it worth my effort to try to use algorithms to improve
performances of modular operations?  As far as I can tell, that should be the major bottle-neck for
elliptic curve operations as I've implemented them.

I was also wondering if anybody knows how performance in sbcl of large integer arithmetic compares to
performance in gmp.  Thank you.
------------------------------------------------------------------------------
EditLive Enterprise is the world's most technically advanced content
authoring tool. Experience the power of Track Changes, Inline Image
Editing and ensure content is compliant with Accessibility Checking.
http://p.sf.net/sfu/ephox-dev2dev
Permalink | Reply | 10 comments |
headers
Nikodemus Siivola | 14 Jun 2011 10:40
Gravatar

Re: modular arithmetic

On 14 June 2011 02:13, Cheung, Matthew G <mgcheung <at> hrl.com> wrote:

> I was wondering if sbcl does any optimisations when performing modular arithmetic.  I
> have written some code that does elliptic curve operations and I was trying to see if I
> could improve performance by implementing any of the algorithms designed to improve
> performance of modular operations such as fast reductions for NIST primes.  What I have
> written appears to be correct since it agrees with the built in mod operator, but it
> actually takes longer.  Is it worth my effort to try to use algorithms to improve
> performances of modular operations?  As far as I can tell, that should be the major
> bottle-neck for elliptic curve operations as I've implemented them.

If your you're operating modulo power-of-two, SBCL should do very well
-- assuming you can convey your intention to it.

Have you read: http://www.sbcl.org/manual/#Modular-arithmetic ?

Looking at it, it isn't actually quite right about the state of the
game since these
days

  (defun foo (x y)
    (declare (fixnum x y))
    (logand most-positive-fixnum (+ x y)))

compiles quite nicely, and while

  (defun foo (x y)
    (declare (type (unsigned-byte 16) x))
    (ldb (byte 16 0) (+ x y)))
(Continue reading)

Permalink | Reply | 6 comments |
headers
Cheung, Matthew G | 14 Jun 2011 18:01

Re: modular arithmetic

>
>If your you're operating modulo power-of-two, SBCL should do very well
>-- assuming you can convey your intention to it.
>
>Have you read: http://www.sbcl.org/manual/#Modular-arithmetic ?
>
>Looking at it, it isn't actually quite right about the state of the
>game since these
>days
>
>  (defun foo (x y)
>    (declare (fixnum x y))
>    (logand most-positive-fixnum (+ x y)))
>
>compiles quite nicely, and while
>
>  (defun foo (x y)
>    (declare (type (unsigned-byte 16) x))
>    (ldb (byte 16 0) (+ x y)))
>
>does get compiled with an AND, it isn't half bad either.
>
>Important things:
>
>1. Declare argument types.
>2. Use LOGAND or LDB to cut the result to the right width.
>

Thanks for your reply.  I did look at what the manual had to say, but I wasn't sure how that was helpful to my
situation.  What I have been trying to do is see if using a fast reduction algorithm for the NIST prime P256
(Continue reading)

Permalink | Reply | 5 comments |
headers
Nikodemus Siivola | 14 Jun 2011 18:17
Gravatar

Re: modular arithmetic

On 14 June 2011 19:01, Cheung, Matthew G <mgcheung <at> hrl.com> wrote:

> Thanks for your reply.  I did look at what the manual had to say, but I wasn't sure how that was helpful to my
situation.  What I have been trying to do is see if using a fast reduction algorithm for the NIST prime P256

> would be faster than the builtin mod operator.  Since I'm assuming my
> input is no bigger than p^2, I did a (declare (type (unsigned-byte 512))
> c) and then in my let I used declare to make all of those variables of
> type (unsigned-byte 256).  Now that I have learned about ldb I now know

Ouch. Not much help from SBCL's modular arithmetic, then -- it's
limited to native word size at most.

> using the ash function to shift to the left.  Would it be more efficient
> to use dpb to write directly to the bytes in question?  I'm starting to

I can't really say offhand -- especially not without seeing the code.
On bignums MOD's speed is essentially down to the speed of
BIGNUM-TRUNCATE. I'm quite not sure how good ours is, but IIRC as long
the bignums aren't particularly huge it should be pretty decent.

> Do you have any more advice on how I can improve efficiency?

Without knowing more of the specifics and seeing the code, not really,
but some general advice:

1. Algorithmic efficiency trumps micro-efficiency 99 times out of 100.
...but you know that already.

2. Profile. Use SB-SPROF to locate bottlenecks.
(Continue reading)

Permalink | Reply | 4 comments |
headers
Matt Kaufmann | 14 Jun 2011 18:31
Picon

Re: modular arithmetic

Regarding:

>> 2. Profile. Use SB-SPROF to locate bottlenecks.

I'd very much like to try that in my own work, but I'm having trouble
getting it loaded.  I tried following the example in Section 15.2.1
(Example Usage) of the SBCL manual at
http://www.sbcl.org/manual/Statistical-Profiler.html, Section 15.2
(Statistical Profiler):

(in-package :cl-user)
(require :sb-sprof)

Below is a log.  I also looked in the manual at documentation for
*MODULE-PROVIDER-FUNCTIONS* and REQUIRE, but I didn't see anything
that would help me.  Am I doing something wrong?

.....

sloth:/projects/acl2/devel> uname -a
Linux sloth 2.6.32-32-server #62-Ubuntu SMP Wed Apr 20 22:07:43 UTC 2011 x86_64 GNU/Linux
sloth:/projects/acl2/devel> sbcl
This is SBCL 1.0.49, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (in-package :cl-user)
(Continue reading)

Permalink | Reply | 3 comments |
headers
Cheung, Matthew G | 14 Jun 2011 18:38

More question about SBCL regarding tail recursion

One thing that has never been clear to me was whether SBCL will by default use tail recursion optimisations. 
I wrote a general "repeated squaring" function that takes as it's arguments a "squaring" function a
"multiply" function, the base and the exponent and I wrote it tail recursively.  This was to be used for both
modular exponentiation and point multiplication on an elliptic curve.  So can I assume SBCL will optimise
by default? 

This question is probably more general lisp, but is it considered a better practice when writing a function
using tail recursion to use a local function to do the actual tail recursion?  Is it a bad idea to use an
optional or keyword parameter to store the results of the intermediate calculations?  In this case it
seemed like it was a good idea since this function would be acting on different types of objects so I could
tell it to start with 1 if I was doing modular exponentiation or the point at infinity for the elliptic curve case.

Thanks.
------------------------------------------------------------------------------
EditLive Enterprise is the world's most technically advanced content
authoring tool. Experience the power of Track Changes, Inline Image
Editing and ensure content is compliant with Accessibility Checking.
http://p.sf.net/sfu/ephox-dev2dev
Permalink | Reply | 11 comments |
headers
Nikodemus Siivola | 14 Jun 2011 18:53
Gravatar

Re: More question about SBCL regarding tail recursion

On 14 June 2011 19:38, Cheung, Matthew G <mgcheung <at> hrl.com> wrote:

> One thing that has never been clear to me was whether SBCL will by
> default use tail recursion optimisations.  I wrote a general "repeated

Tail-merging is done if (> SPACE DEBUG) or (> SPEED DEBUG) -- not by default.

> This question is probably more general lisp, but is it considered a
> better practice when writing a function using tail recursion to use a
> local function to do the actual tail recursion?  Is it a bad idea to use

Depends on the case, but if eg. floating point arguments are involved
a local call may be more efficient.

> an optional or keyword parameter to store the results of the
> intermediate calculations?  In this case it seemed like it was a good

Stylistically it's fine.

From micro-efficiency POV it is less than ideal. &OPTIONAL is pretty
cheap, but unless the function is inlined &KEY incurs a runtime cost
for keyword parsing.

Cheers,

 -- nikodemus

------------------------------------------------------------------------------
EditLive Enterprise is the world's most technically advanced content
authoring tool. Experience the power of Track Changes, Inline Image
(Continue reading)

Permalink | Reply | 8 comments |
headers
Waldek Hebisch | 14 Jun 2011 18:17
Picon

Re: modular arithmetic

Cheung Matthew G wrote:

> I was also wondering if anybody knows how performance in sbcl of
> large integer arithmetic compares to performance in gmp.

It depends on how large is "large".  Multiplying small bignums (about 20
machine words, that is few hundred digits) sbcl is comparable to gmp.
On large bignums gmp is much faster.  Also, in gmp ratio of time to do
division, gcd or integer sqrt to multiplication time is much smaller
than in sbcl.  In particular at time when I tested it integer sqrt in
gmp was faster than sbcl for all sizes (in fact, gmp could compute
integer sqrt of small bignum faster than sbcl computed integer sqrt of
a fixnum).  Recenctly, there was an improvement to integer sqrt in
sbcl so result could change, but probably not much.

It is possible to use gmp from sbcl, replacing sbcl routines by
gmp ones.  I did this for FriCAS computer algebra system (in
computer algebra speed on large bignums is important).  I also
created a version of interface to gmp which is independent
from FriCAS:

http://www.math.uni.wroc.pl/~hebisch/prog/cl-gmp-0.0.tar.bz2

This version has a bug causing wrong results when used with
gmp 4.3, but should work fine with gmp-4.2 and gmp-5.0.  I have
a bugfix, but given apparent lack of interst I did not bother
creating new release.  However, if you are interested I will
create a new version with bugfix included.

--

--
(Continue reading)

Permalink | Reply | 2 comments |

Gmane