Home

Advertisement

Customize

Liam Healy

Nov. 25th, 2009

06:29 pm - Sanitizing history in git

It may happen that you wish to replace some string throughout a git repository and its history. This can be done with a combination of rpl and git filter-branch. The former recursively replaces strings in a directory and the latter applies it to all items in the history. So for example,

git filter-branch --tree-filter 'rpl -iR oldstring newstring *' HEAD

will do the job. If this branch tracks a remote, then untrack it,
  git remote rm origin
  rm -rf .git/refs/original

Now this is a freestanding branch which can be pushed to a new remote. Note that everyone who cloned from an existing remote that has been replaced will need to discard their files and clone again, because all the IDs for the entire history will have changed. Also it appears that newstring has to be non-empty; I tried "" but it doesn't work in filter-branch because rpl wants to query the user to make sure it's OK to replace with an empty string.

Tags:

May. 3rd, 2009

05:19 pm - GSLL using FSBV

The GNU Scientific Library for Lisp (GSLL) now makes use of Foreign Structures By Value (FSBV) to define functions that pass or return complex scalars, which are represented as structures in GSL. The tests in gsll-tests will test some of these functions, and they all pass.

Since my last posting, there have been some improvements to FSBV; among them, the copying between Lisp and foreign code happens automatically in the definition with either fsbv:defcfun or fsbv:foreign-funcall. Since there is some preparation involving structures needed for libffi, and this need be done only once per function when it is defined, fsbv:defcfun makes a closure separately when it is loaded and then the invocation of the function just calls that closure on the specific arguments. If fsbv:foreign-funcall is called with the symbol used for the Lisp name of the fsbv:defcfun, it will also use that closure. GSLL takes advantage of that efficiency. Since I think FSBV won't change too much now (at least in the interface) I have tagged it with "0.1" release.

For those GSLL users who have no need for complex functions and don't want to bother installing libffi and FSBV, GSLL will compile and load fine without them; of course, those functions won't be available.

Tags:

Apr. 28th, 2009

09:23 pm - Foreign structures by value

I have written Foreign Structures By Value which will allow calling foreign functions that either take or return structures by value instead of by reference (i.e., with a pointer). It requires CFFI and libffi, and should work in any environment where those are both supported.

For example, the complex type is defined in the GNU Scientific Library (GSL) as

typedef struct
  {
    double dat[2];
  }
gsl_complex;

The function gsl_complex_conjugate takes and returns a structure of this type by value,

gsl_complex gsl_complex_conjugate (gsl_complex z);

If we define

(fsbv:defcstruct (complex :constructor complex :deconstructor (realpart imagpart))
  (dat :double :count 2))
(defun complex-conjugate (complex-number)
  (fsbv:with-foreign-objects ((gslin 'complex complex-number))
    (object
     (fsbv:foreign-funcall "gsl_complex_conjugate" complex gslin complex)
     'complex)))

then we can call this function from Lisp:
(complex-conjugate #c(3.0d0 4.0d0))
#C(3.0 -4.0)

This is making its way into GSLL but in the meantime should be usable for other projects.

Tags:

Mar. 16th, 2009

09:00 pm - Regression (unit) test in Lisp, including float tests

In the course of writing GSLL, I found that I needed some software for regression (unit) tests. I mentioned before that I had made use of lisp-unit, augmenting with a test of floating point equivalence. Tom Hermann has similar needs; he saw what I had done and merged it with his own, better, floating point test. He has put this together into an augmented lisp-unit. The git repository has been set up with the permission of Christopher Riesbeck, the author of lisp-unit. Instead of including my extended lisp-unit now, GSLL (specifically, gsll-tests) makes use of this separate repository. Other projects could similarly benefit.

Tags:

Jan. 15th, 2009

06:15 pm - Passing a complex number to a foreign function

GSL has a number of functions that take complex scalars as arguments. It defines them with either

typedef struct
  {
    double dat[2];
  }
gsl_complex;

or
typedef struct
  {
    float dat[2];
  }
gsl_complex_float;

These complex numbers are always passed by value, not as a pointer. This presents a problem to Lisp users as many foreign function interfaces and CFFI do not allow passing structs directly.


I thought maybe there was a way around this. Could it be that the real and imaginary parts are simply passed sequentially as if they were two successive arguments to the function? In fact, this does work for numbers of type (complex double-float), but when I tried that on (complex single-float), it would return without error but with the result computed as if the imaginary part was 0. I thought maybe there was a padding issue, so I packed the two single-floats into a single 64-bit word that I then interpreted as a double-float. When passing this single argument to a function that expects a (complex single-float), the correct answer is computed.


For example, the BLAS function caxpy works on single-floats:

(FOREIGN-FUNCALL "gsl_blas_caxpy" 
		 :DOUBLE (PACK-COMPLEX-AS-DOUBLE ALPHA) 
		 :POINTER (MPOINTER X) :POINTER (MPOINTER Y)
		 :INT)

where #'pack-complex-as-double does the packing on the complex scalar alpha described, and the function zaxpy works on double-floats
(FOREIGN-FUNCALL "gsl_blas_zaxpy" 
		 :DOUBLE (REALPART ALPHA) 
		 :DOUBLE (IMAGPART ALPHA) 
		 :POINTER (MPOINTER X) :POINTER (MPOINTER Y) 
		 :INT)


This has now been incorporated into GSLL. I assume it is not portable; I am on Debian amd64 but it works on x86 (32 bit) as well. It seems to be portable across CL implementations, at least it works in SBCL and CCL. So I have built in a test that tries a simple function; if it gets the wrong answer than all the functions that want a complex scalar will signal an error.

Tags: ,
Current Mood:

Jan. 4th, 2009

03:00 pm - GSLL new version

The new version GNU Scientific Library for Lisp (GSLL) is now available. This library has many mathematical functions used in science and engineering applications. It works on several Lisp implementations.


The most significant changes from the previous version include:


  • All objects are memory managed (garbage collected), which means they can have indefinite extent like any other Lisp object. There is no need to put the object creation in a letm; in fact letm doesn't exist anymore. Use let, or defparameter, etc.
  • All array (vector and matrix) element types that are supported by the platform, CL implementation, CFFI, and GSL, are supported by GSLL.
  • On SBCL both Lisp and C use the same representation for array contents; they are not copied between the two sides. Thanks to Tamas Papp's foreign-friendly arrays for the inspiration.


There have been some function name and argument changes, so users of the previous version will need to update their code. Please use the git repository and discontinue using the old svn repository.

Feedback welcome, here or on the mailing list.

Tags: ,

Sep. 30th, 2008

04:48 pm - Clozure CL on Debian


A while back, I mentioned trying OpenMCL for Debian. OpenMCL is now Clozure CL (CCL), and version 1.2 for MacOSX and Linux (PPC and amd64) was recently announced. I gave it another try and the experience is much better, though it needs Debianization.


The Debian Common Lisp Team has produced a Common Lisp in Debian manual, so I followed that to Debianize CCL. As root,

> lx86cl64
Welcome to Clozure Common Lisp Version 1.2-r10552  (LinuxX8664)!
? (load "/usr/share/common-lisp/source/common-lisp-controller/common-lisp-controller.lisp")
? (common-lisp-controller:compile-common-lisp-controller-v5 "ccl")
(#P"/var/cache/common-lisp-controller/0/ccl/common-lisp-controller/common-lisp-controller.lx64fsl"
 #P"/var/cache/common-lisp-controller/0/ccl/cl-asdf/asdf.lx64fsl"
 #P"/var/cache/common-lisp-controller/0/ccl/cl-asdf/wild-modules.lx64fsl"
 #P"/var/cache/common-lisp-controller/0/ccl/common-lisp-controller/post-sysdef-install.lx64fsl")

Now as an ordinary user,
? (load "/var/cache/common-lisp-controller/0/ccl/common-lisp-controller/common-lisp-controller.lx64fsl")
? (load "/var/cache/common-lisp-controller/0/ccl/cl-asdf/asdf.lx64fsl")
? (load "/var/cache/common-lisp-controller/0/ccl/cl-asdf/wild-modules.lx64fsl")
? (load "/var/cache/common-lisp-controller/0/ccl/common-lisp-controller/post-sysdef-install.lx64fsl")
? (common-lisp-controller:init-common-lisp-controller-v5 "ccl")
? (ccl:save-application "ccl-deb")

When restarted with

lx86cl64 ccl-deb

all the Debian definitions are there. (I recommend using rlwrap from a shell for easier input editing.)



I tried to compile and load various debian packages and other systems, with reasonably good success;

(clc:clc-require :asdf-system-connections)
(clc:clc-require :cl-base64)
(clc:clc-require :cl-ppcre)
(clc:clc-require :md5)
(clc:clc-require :port)
(clc:clc-require :iterate)
(clc:clc-require :cl-utilities)
(clc:clc-require :uffi)
(clc:clc-require :clsql-uffi)
(clc:clc-require :clsql-sqlite3)
(clc:clc-require :cffi)
(clc:clc-require :drakma)
(clc:clc-require :cl-html-parse)

all worked fine; I did get errors from a few things
(clc:clc-require :memoization)
 Error: The function CCL:ARGLIST is predefined in OpenMCL.
(use-package :iterate :cl-user)
> Error: Using #<Package "ITERATE"> in #<Package "COMMON-LISP-USER">
>        would cause name conflicts with symbols inherited by that package: 
>        ITERATE:TERMINATE  TERMINATE
 (clc:clc-require :trivial-http)
> Error: Module TRIVIAL-HTTP was not provided by any function on *MODULE-PROVIDER-FUNCTIONS*.

I'm sure many of my applications (tested mainly on SBCL and a little CLISP) will need fixing up.

Tags: ,

Aug. 12th, 2008

09:12 am - AFS rides again


After using AFS for a number of years, I gave up on it several years ago in frustration, because it was complex and difficult to install with the Linux kernel of the time. However, in the meantime, OpenAFS has become dominant, and it works well with Linux and Debian. Installation is easy thanks to module-assistant:

 aptitude install module-assistant build-essential
 aptitude install krb5-user krb5-clients
 aptitude install openafs-client openafs-modules-source openafs-krb5
 m-a prepare
 m-a a-i openafs
 invoke-rc.d openafs-client start

The whole world is now under /afs. To authenticate to the default cell,
 kinit
 aklog

Having access to several AFS servers, I'm still trying to figure out how to get simultaneous access to all of them. It seems that you can only kinit to one realm at a time. However, it need not be your default realm;
kinit user@OTHER.REALM
aklog -cell other.afs.server -k OTHER.REALM

works.


AFS wants cache space, which it insists be ext2 or ext3. If you don't have those (I have xfs), don't worry, you can make one in a file on any filesystem:

  dd if=/dev/zero of=/some/local/dir count=nnnn bs=1M 
  mkfs.ext3 /some/local/dir
  mount /some/local/dir /var/cache/openafs -o loop

When you configure the client, give a size 95% of nnnn, it won't allow any larger. Also when configuring the client, say yes to "Dynamically generate the contents of /afs?" (AFS_DYNROOT). This will free you from your home cell's listing of sites, and use /etc/openafs-client/CellServDB, but it will effectively dynamically mount them: it won't actually contact the server until you refer to a site.

Aug. 2nd, 2008

01:19 pm - Using git to stitch together a broken subversion repository

I have recently learned git for version control, having used Subversion for four years and CVS for four years prior to that. It has a lot of nice features and I thought of a good application: restoration of lost history on a Subversion repository.

In the process of moving my project GSLL from a private subversion repository to a public one on common-lisp.net, I lost the entire history. I was trying to extract the GSLL part from my whole repository, which had several other projects. I had tried an svnadmin dump and then svndumpfilter, but this did not work for me, leaving me with no history and the version number at 25 from the failed filtering attempts.

When I saw a blog at newartisans describe the usage of git for a similar task, I decided to try to transfer my repository to git (with the intention of abandoning subversion) and at the same time restore the entire history. I was able to do it, but it took some work and I was unable to use git rebase exclusively as the newartisans blogger did, because I had a branched history, with two subversion branches "trunk" and "ffa" and a tag "pre-iospec". Here is how I did it, edited (I hope correctly) to eliminate my trial-and-error-failures:


  1. Get a fresh copy of the new svn repository and check out the branches
     git svn clone --stdlayout svn+ssh://public/repo/ /tmp/clnetsvn
     cd /tmp/clnetsvn
     git checkout -b trunk trunk
     git checkout -b ffa ffa
    

    If you use --no-metadata to git-svn, there will be no additions to the commit message indicating the Subversion source and version numbers. If you want to completely forget about the svn repository, that might be desirable, but I wanted to be able to identify the svn versions to aid in the stitching process.

  2. Get a fresh copy of the old private svn repository for which new commits stopped when the new repository was created
     git svn clone --stdlayout svn+ssh://private/repo/ /tmp/localsvn
     cd /tmp/localsvn
     git checkout -b trunk trunk
     git checkout -b pre-iospec tags/pre-iospec
    

    I decided to keep the tag pre-iospec though I don't really need it anymore.

  3. Create a staging area to do some git surgery
     mkdir ~/staging; cd ~/staging; git init
     git remote add localsvn /tmp/localsvn
     git remote add clnetsvn /tmp/clnetsvn
     git fetch localsvn
     git fetch clnetsvn
     git checkout --no-track -b old localsvn/trunk
     git checkout --no-track -b pre-ffa clnetsvn/trunk
     git checkout --no-track -b master clnetsvn/ffa
    

    Note I have renamed the two active branches to "pre-ffa" (from "trunk") and "master" (from "ffa") , reflecting my intention that ffa will soon become the main branch of development, and the previous trunk will be archived for historical purposes and won't see much further development.

  4. Do the stitching
    First, confirm that the last commit of old is the same as the first substantive commit of either pre-ffa or master
     git diff old..6ed4d0626
    

    There is no output, indicating that the two commits are identical; 6ed4d0626 was the second checkin on clnetsvn. The first is just the creation of trunk and has no contents. If there had been a difference (indicating something had changed between the two commits), I would have had to check it in, as is the case on the newartisans blog. Now rebase the ffa branch onto old (it could as well have been trunk, but only one should be rebased):
     git rebase old master
    

    Based on the advice of Jakub Narebski, I created a file .git/info/grafts which consists of two SHA1 ids:
     0069b7f5af9a90dde26de14c7c19ae92e4d9f38b eef416b5cb25797ae266cda2f28e0c56c1675437
    

    The id of the first commit in trunk split off from ffa is 0069b7f5...; it has a parent commit that is duplicated on the ffa branch that is unified with the old repostory, but meanwhile its lineage ends with the start of the clnetsvn respository. The id of its parent is eef416b5... on the unified branch. This may be easily confirmed if --no-metadata was not used, because the Subversion information stamp in its actual parent and in the same commit on the unified branch have identical subversion information. The grafts file needs the entire 40 hex digit SHA1 ID; it doesn't work with an abbreviated id. At this point, an inspection with gitk --all shows the correct hierarchy; everything looks fine because the presence of the grafts file connects the lineage correctly. However, a git push would result in a broken repository, because the grafts file is not pushed. So, do
     git checkout pre-ffa
     git filter-branch 646c623c193139ba491c3bccc6ff6dd26bfa4bdc..HEAD
    

    with 646c623... being the first commit in the now-rebased master. Note that this differs from the advice in the git-filter-branch man page which says to use the graft id, but that didn't work for me and this does; I suspect an error on the man page or a change in how git filter-branch works.

    To summarize:

    1. Do a rebase to connect the current master branch onto its old history from the first svn repository;
    2. Do the graft because two git-rebases on each branch would have left duplicated histories back to the start of the new (public) repository
    3. Apply filter-branch so that this would be permanent when the repository is pushed.


  5. Push to remote repository
     git remote add origin ssh://remote/repository
     git push --all origin
     git push --tags
    



And that's it, everything looks correct. Git is very nice.

Tags:

May. 15th, 2008

09:35 pm - SBCL in Debian testing (lenny): good news

Thanks to lots of work and attention from various people:

http://release.debian.org/migration/testing.pl?package=sbcl
Checking sbcl

* trying to update sbcl from 1:0.9.16.0-1 to 1:1.0.16.0-2 (candidate is 12 days old)
* sbcl is going in today

Tags: ,

May. 3rd, 2008

07:33 pm - SBCL in Debian testing (lenny)

Recently I noticed that SBCL in Debian testing is quite old; it is currently at 0.9.16 and evidently blocked there:

=== sbcl:
= Missing build(s) on alpha,sparc
 This might need manual action from your side.
 See http://buildd.debian.org/pkg.cgi?pkg=sbcl
= No migration to testing for 585 days.
 See <http://release.debian.org/migration/testing.pl?package=sbcl>

I have tried to stir the pot, and there has been some progress. This version of testing will release as lenny in the fall, and it would be a shame if it released with such an old version of SBCL.

Tags: ,

Mar. 22nd, 2008

08:50 am - Cairo for Lisp

I have been looking into using Cairo for various 2D drawing needs. A key advantage is the availability of a variety of output formats, including both screen and hardcopy. One potential application is traditional x-y scientific/engineering plots. Although there are many options for doing that, even using Lisp, I have a Lisp package I adapted many years ago for this purpose that now lacks a good back end for output. My thought is that Cairo would be good for that, as it is a standardized library, widely available, with many modern output formats. I also have other 2D output that I do from Lisp, which I now do with a thin postscript definition layer that I wrote. Switching to Cairo would give me some more flexibility.


I did some research and found that there were three sets of bindings for Cairo:


The first, cl-cairo, despite being linked from the cairographics web page, appeared to be dead. I found the author, Lars Nostdal, on #lisp who said the project was no longer active, so with his permission I modified the Cairo bindings page to mention cl-cairo2 and cffi-cairo and remove cl-cairo. cl-cario2, from Tamás K Papp, seems more active, but I had trouble getting it to run; I've posted my problems and am awaiting a response. Finally, I tried cffi-cairo from chriss. It did not compile, but it was easy to fix the problem: the CFFI interface has changed, defctype no longer has a :translate-p argument. With a slight modification, the example
(run-snippet-png '(:clip :clip-image)) ran and produces PNG files that looked correct.


It looks like I'll be using cffi-cairo.

Tags: ,

Mar. 8th, 2008

02:16 pm - Never a NaN or Inf

In very few cases is it acceptable to me that a floating-point calculation would produce NaN or Inf; it almost always means that there is an error somewhere in my program. Following the principle that it is best to detect an error as soon as possible, I would like to know immediately whenever either of these is created, by trapping the exception and signaling an error. Depending on the language and implementation, this doesn't always happen by default. Here are some different languages and compilers, and how to set to make this happen:


  • Lisp: SBCL: (sb-int:set-floating-point-modes :traps '(:invalid :divide-by-zero :overflow)) and
    CMUCL: (ext:set-floating-point-modes :traps '(:invalid :divide-by-zero :overflow)).
    Also GSLL provides #'set-floating-point-modes.
  • Fortran: for gfortran, use the compiler flag -ffpe-trap=invalid,zero,overflow.
  • C/C++: use
    #include <fenv.h>
    trapfpe () {
      feenableexcept(FE_INVALID|FE_DIVBYZERO|FE_OVERFLOW);
    }
    

    In C, this will need to be included: void trapfpe();
    In C++, this will need to be included (also works for C):
    #ifndef _TRAPFPE_H_
    #define _TRAPFPE_H_
    
    #include <sys/cdefs.h>
    
    __BEGIN_DECLS
    void trapfpe(void);
    __END_DECLS
    
    #endif /* _TRAPFPE_H_ */
    

    and then in either, include trapfpe(); at the beginning. This should be portable to C99 compilers/libc but I've used only gcc and glibc. Also, GSL has gsl_ieee_env_setup.

Mar. 5th, 2008

08:54 am - SBCL, libc6, and GCC


For those that don't follow the mailing list, SBCL on Debian is unusable in unstable. SBCL did not change, but Debian upgraded libc6 to 2.7-9. This causes SBCL to spin at 100% usage, or simply to hang, while starting up. The only relevant change to libc6 is that it is now compiled with GCC 4.3 instead of 4.2; the libc6 maintainer has confirmed that backing out this change and recompiling libc6 with GCC 4.2 allows SBCL to work. It is still unclear where the problem(s) is/are; but the experts have narrowed it down further. Follow the developments on the Debian bug report; even if you don't use Debian, presumably this combination of software is a problem. In the meantime, if you are a sid user, don't upgrade! Though apparently some people have experienced the problem as a random failure, my experience is that it's 100% reproduceible.


Software is complicated.

Tags: ,

Feb. 24th, 2008

06:27 pm - GNU Scientific Library for Lisp

The GNU Scientific Library is a library of applied mathemetics commonly used in science and engineering. I have written GNU Scientific Library for Lisp (GSLL), a fairly complete interface to this library from Common Lisp. My intent is that the interface be as Lisp-natural as possible. Though this will be useful for those of us that do scientific programming in Lisp, even those who aren't Lisp programmers might use this library as a desk-calculator interface to GSL.

Tags: ,

Jan. 26th, 2008

01:29 pm - Comparison of floating point numbers in Common Lisp

Floating point numbers are a computer representation of the real numbers. Unlike the real numbers, there are a finite number of them. So there is a smallest and largest floating point number, and all others have a predecessor and successor.

Because different compilers and platforms can reorder a calculation and optimize in a way that is approximated differently and so do not necessarily produce the same floating point number, it is difficult to compare two floating point numbers and conclude that they represent the same result. For the purposes of regression (or unit) testing, we would like to do exactly this. Bruce Dawson addressed this problem in "Comparing Floating Point Numbers." He makes the point that the best way to do this correctly is to interpret each floating point number as an integer. By taking advantage of the IEEE 754 standard for representation of floating point numbers, we can construct a function that maps the floating point numbers to the integers. The genius of the standard's inventor W. Kahan is that a mapping derived from the standard, call it i(x), satisfies three properties:

  • If two floats a<b, then i(a)<i(b),
  • if two floats are adjacent and a<b, then i(b)=i(a)+1,
  • and finally i(0.0)=0.

Dawson provides some clever C constructs to read a floating point number as an integer, and instruction on how to prevent the compiler from complaining about your trickery in doing so. Common Lisp instead provides us with functions with which we can properly construct our own integers. As a side benefit, we don't care what the actual representation of the floating point number is; we will build our own IEEE-like representation. We don't exactly want the full IEEE754 word though; we leave off the most significant bit, which is a sign bit, and instead make the sign of the integer agree with the sign of the float.

What we end up with is an enumeration of the floats. That is, for every single precision float, there is one integer in the range [-2139095039, 2139095039], and vice versa, with the exception that both positive and negative zero (allowed by the standard) map to zero. Likewise, there is a one-to-one mapping of the double precision floats to [-9218868437227405311,9218868437227405311]. Floats with special values (positive and negative infinity, and NaN) that are required by the standard do not have integer values.

I have written the following functions in Common Lisp:

  • float-as-integer which is the function i(x);
  • integer-as-float which is the inverse function (this isn't necessary but can be useful) and also returns the rational form of the float;
  • decode-IEEE754 (used by other functions) that returns five values: significand, exponent, sign, bits in significand, bits in exponent, all as integers;
  • format-IEEE754-bits which prints out the binary form of the IEEE word, separated into the three parts (this isn't necessary but is nice for comparing with bit expansions shown in references like the Wikipedia page).

Here are some interesting floats:

(float-as-integer most-negative-single-float)
-2139095039
(float-as-integer least-negative-single-float)
-1
(float-as-integer -0.0f0)
0
(float-as-integer 0.0f0)
0
(float-as-integer least-positive-single-float)
1
(float-as-integer (- 1.0f0 single-float-negative-epsilon))
1065353215
(float-as-integer 1.0f0)
1065353216
(float-as-integer (+ 1.0f0 single-float-epsilon))
1065353217
(float-as-integer most-positive-single-float)
2139095039

A regression test would record not the floating point number, but the integer produced by float-as-integer. Since integers can be unambiguously formatted to and read from a text file in a unique way, a subsequent recomputation would provide a clear indication of how close the floats are. Of course, we must decide how much error we're going to allow, because a correct calculation may produce slightly different integers. As an added bonus, these functions can be used to identify (in languages other than Lisp) when a positive single float has been interpreted as a double float.

Jan. 22nd, 2008

06:00 pm - Multiprocessing lisp evaluations

I sometimes need to evaluate the same form with different parameters repeatedly. Such as

(job 1)
(job 2)
(job 3)
...

When these are time consuming, I'd like to take advantage of the two processors I have in my computer. As the jobs are independent of each other (no communication), I only need to maintain a job queue, have each processor pick off the front of the queue, and then place the results in an accessible place before getting the next job. Since SBCL has threads, at least for Linux on x86 and amd64, I should be able to use this mechanism to build the job queue. Following Rochkind Section 5.17, I have written the following:
(defparameter *job-lock* (sb-thread:make-mutex :name "job lock"))
(defparameter *results* (list nil))
(defvar *end-of-jobs* (make-symbol "EOJ"))
(defvar *jobs* nil)

(defun worker (job)
  (let ((my-job nil)
	(more-jobs t))
    (loop while more-jobs
       do
       (sb-thread:with-mutex (*job-lock*)
	 (setf more-jobs (or *jobs*))
	 (setf my-job (when more-jobs (pop *jobs*))))
       (when my-job			; there is a job to be done
	 (if (eq my-job *end-of-jobs*)
	     (setf more-jobs nil)
	     (let ((my-results (apply job my-job))) ; call the job outside the mutex
	       (sb-thread:with-mutex (*job-lock*)   ; save results
		 (push my-results *results*))))))))

(defun run-tasks (job dataset number-of-workers)
  "The job is a function that takes one non-null argument.
   The dataset is a list of arglist sets for the job.
   The number-of-workers is the number of workers desired, 
   presumably the number of processors available."
  (setf *jobs* (make-list number-of-workers :initial-element *end-of-jobs*)
	*results* (list nil))
  (dolist (ds dataset) (push ds *jobs*))
  (let ((threads (list nil)))
    (loop repeat number-of-workers
       do (push (sb-thread:make-thread (lambda () (worker job))) threads))
    (dolist (thread (butlast threads)) (sb-thread:join-thread thread))
    (butlast *results*)))

Try this example:
(defun job (x) (list x (+ (loop for i from 1 to 2000000 sum (let ((p (* i x))) (1- (expt p (/ p))))))))
(run-tasks #'job '((1) (2) (3) (4) (5) (6) (7) (8) (9) (10)) 2)
((1 105.73587) (2 58.11023) (3 41.245914) (4 31.676012) (5 26.053244)
 (6 22.305136) (7 19.607342) (8 17.642727) (9 15.433696) (10 14.060191))

Unfortunately, after I coded this up and tried it on my actual function, I found that that function was not thread safe, due to use of a foreign library that wasn't thread safe.

Tags:

Jan. 5th, 2008

12:45 pm

I have my new OLPC XO-1 now, from the "Give one get one program". My intended use is mainly for updates from the road while on bike tours.

One thing I'd like is instant messaging. The "Chat Activity" works to other XOs but evidently not to anyone else. Pidgin and Finch have been ported, so I tried Finch, being text-based and therefore presumably simpler. It works, but unfortunately it is based on ncurses. Evidently, few if any of the curses controls work on th XO, so I can't even expand the "window" to full screen. It would be nice if there were a plain text (no pseudo-windowing, no curses, etc.) IM client, perhaps one based on libpurple?

Update: I found NAIM which is full screen and does not try to emulate windowing, but has an odd choice of colors - the typein area is white letters on a white background, which makes it hard to see.

Tags: , ,

Nov. 6th, 2007

06:54 pm - Profiling in SLIME

This is about the easiest profiling I've seen in any language. In
fact, I think it's the only time I been able to make significant
improvements based on the report.

M-x slime-toggle-profile-fdefinition
on all the functions you want to
profile,
M-x slime-profile-reset
to clear any existing data, and
M-x slime-profile-report
to see the report after running.
I did it on one of my functions which was taking 700+ seconds to run.
I immediately saw that I was doing an unnecessary computation, which
when removed resulted in a 90 second run. Some more profiling and
other work yielded an end result of 2.5 seconds.

Tags:

Oct. 25th, 2007

12:44 pm - DoD authentication in Iceweasel/Icedove

Common DoD authentication with certificates and the Common Access Card (CAC) is possible in Debian for Iceweasel (Firefox) and Icedove (Thunderbird). It can be reduced to the following:


  1. Install the DoD Configuration add-on in Iceweasel by clicking on "Install Now" button.
  2. Save that xpi file from Iceweasel by clicking right on the button. Install the file in Icedove: Tools -> Add-ons -> Install.
  3. Test from web by visiting http://www.navy.mil; the URL should be green. You do not need your CAC.
  4. Load packages in Debian:
    sudo aptitude install libpcsclite1 pcsc-tools libccid coolkey
    

    This will enable the CAC reader in Debian unstable; I don't know if the versions of previous Debian releases will work. Note that not all CAC readers are supported; see the list. In particular, the ActivCard 2.0 USB, which is very common, is not supported.
  5. With your CAC inserted, visit http://infosec.navy.mil. You will be prompted for your PIN, and you should be able to select your certificate. To see the certificate information that the server has, visit the PKI Cert test page.
  6. You can sign/encrypt email by using the S/MIME button, and set up defaults for every email with Edit -> Account Settings -> Security. Note that OpenPGP security is completely separate from CAC security, and the icons that display in messages and the composition area shouldn't be confused.


That should do it. References: Van Alstyne, CoolKey package.

Tags:

Navigate: (Previous 20 Entries)