Tag Archives: Julia

Using Julia’s C Interface to Utilize C Libraries

By: Christopher Rackauckas

Re-posted from: http://www.stochasticlifestyle.com/using-julias-c-interface-utilize-c-libraries/

I recently ran into the problem that Julias’s (GNU Scientific Library) GSL.jl library is too new, i.e. some portions don’t work as of early 2016. However, to solve my problem I needed access to adaptive Monte Carlo integration methods. This means it was time to go in depth in Julia’s C interface. I will go step by step on how I created and compiled the C code, and called it from Julia.

What I wished to use was the GSL Vegas functions. Luckily, there is a good example on this page for how to use the library. I started with this code. I then modified it a bit. To start, I changed the main function header to:

int monte_carlo_integrate (double (*integrand)(double *,size_t,void *),double* retRes,double* retErr,int mode,int dim,double* xl,double* xu,size_t calls){

Before it took in no values, but I will want to be able to do most things from Julia. First of all, I changed the function name from main to avoid namespace issues. This is just good practice when working with shared libraries. then I added a bunch of arguments. The first argument is a function pointer, where the function is defined just as g is in the example. Then I pass in pointers which we become the return values. I add mode (1,2,3 are the different integration types), dim, xl, xu, and calls as passed in values to easily extend the functionality. The rest of the C-code stays mostly the same: I change the parts which reference g to integrand (I like the function name better) and comment out the print functions (they tend to no print correctly). So I end up with a C-function as follows:

#include <stdlib.h>
#include <gsl/gsl_math.h>
#include <gsl/gsl_monte.h>
#include <gsl/gsl_monte_plain.h>
#include <gsl/gsl_monte_miser.h>
#include <gsl/gsl_monte_vegas.h>
int monte_carlo_integrate (double (*integrand)(double *,size_t,void *),double* retRes,double* retErr,int mode,int dim,double* xl,double* xu,size_t calls){
  double res, err;
  const gsl_rng_type *T;
  gsl_rng *r;
  gsl_monte_function G = { *integrand, dim, 0 };
  gsl_rng_env_setup ();
  T = gsl_rng_default;
  r = gsl_rng_alloc (T);
  if (mode==1){
    gsl_monte_plain_state *s = gsl_monte_plain_alloc (dim);
    gsl_monte_plain_integrate (&G, xl, xu, dim, calls, r, s,
                               &res, &err);
    gsl_monte_plain_free (s);
    /* display_results ("plain", res, err); */
  }
  if (mode==2){
    gsl_monte_miser_state *s = gsl_monte_miser_alloc (dim);
    gsl_monte_miser_integrate (&G, xl, xu, dim, calls, r, s,
                               &res, &err);
    gsl_monte_miser_free (s);
    /* display_results ("miser", res, err); */
  }
  if (mode==3){
    gsl_monte_vegas_state *s = gsl_monte_vegas_alloc (dim);
    gsl_monte_vegas_integrate (&G, xl, xu, dim, 10000, r, s,
                               &res, &err);
    /* display_results ("vegas warm-up", res, err); */
    /* printf ("converging...n"); */
    do
      {
        gsl_monte_vegas_integrate (&G, xl, xu, dim, calls/5, r, s,
                                   &res, &err);
        /* printf ("result = % .6f sigma = % .6f "
                "chisq/dof = %.1fn", res, err, gsl_monte_vegas_chisq (s)); */
      }
    while (fabs (gsl_monte_vegas_chisq (s) - 1.0) > 0.5);
    /* display_results ("vegas final", res, err); */
    gsl_monte_vegas_free (s);
  }
  gsl_rng_free (r);
  *retRes = res;
  *retErr = err;
  return 0;
}

Notice how nothing was specifically changed to be “Julia-style”, this is all normal C-code. So how do I use it? First I need to compile it to a shared library. This means I use the -shared tag and save it to a .so. I will need the GSL libraries loaded when compiling, so I add the -lgsl, -lgslcblas, and -lm (math) tags to link those libraries. Then I add the -fPIC tag since Julia’s documentation says so, and tell it the file to compile. The complete code is:

gcc -Wall -shared -o libMonte.so -lgsl -lgslcblas -lm -fPIC monteCarloExample.c

This will give you a .so file. Now we need to use it. I will describe passing in the function last. Here’s the setup. The first of the other variables are the two pointers retRes and retErr where the results will be saved. In Julia, to get a pointer, I make two 1-element arrays as follows:

x = Array{Float64}(1)
y = Array{Float64}(1)

The only other peculiar thing I had to do was to change pi from Julia’s irrational type to a Float64 (Cdouble) and use that to make the array. So for the other variables I used:

fpi = convert(Float64,pi)
xl = [0.; 0.; 0.]
xu = [fpi; fpi; fpi]
calls = 500000
mode = 3
dim = 3

Now I pass this all to C as follows:

ccall((:monte_carlo_integrate,"/path/to/library/libMonte.so"),Int32,(Ptr{Void},Ptr{Cdouble},Ptr{Cdouble},Int32,Int32,Ptr{Cdouble},Ptr{Cdouble},Csize_t),integrand_c,x,y,mode,dim,xl,xu,calls)

The first argument a tuple where the first place is the symbol which says which function in the library to use and the second place is the library name or the path to the library. The second argument is the return type (here it’s Int32 because our function returns int 0 when complete). The next portion is a tuple which defined the types of the arguments we are passing. The first is Ptr{Void} which is used for things like function pointers. Next there are two Cdouble pointers for retRes and retErr. Then two integers, two more pointers, and a Csize_t. Lastly we put in all of the variables we want to pass in.

Recall that the result was stored into the pointers for the second and third variable passed in. These are the pointers x and y. So to get the values of res and err, I de-reference them:

res=x[1]
err=y[1]

Now res and err hold the values for the solution and the error.

I am not done yet since I didn’t talk about the function! To do this, we define the function in Julia. We have to use parametric types or Julia will yet at us, and we have to ensure that the returned value is a Cdouble (in our case). So we re-write the g function in Julia as:

function integrand{T,T2,T3}(x::T,dim::T2,params::T3)
  A = 1.0 / (pi * pi * pi)
  return A / (1.0 - cos(unsafe_load(x,1))*cos(unsafe_load(x,2))*cos(unsafe_load(x,3)))::Cdouble
end

Notice that instead of x[1], we have to use the Julia function unsafe_load(x,1) to de-reference a pointer. However, since this part is in Julia, other things are much safer, like how we can use pi directly without having to convert it to a float. Also notice that we can add print statements in this function, and they will print directly to Julia. You can use this to modify the display_results function to be a Julia function which prints. However, this itself is still not able to be passed into C. To do that, you have to translate it to a C function:

integrand_c = cfunction(integrand,Cdouble,(Ptr{Cdouble},Ptr{Cdouble},Ptr{Cdouble}))

Here we used the Julia cfunction function where the first argument is the function, the second argument is what the function returns, and the third argument is a tuple of C-types that the function will take on. If you look back at the ccall, this integrand_c is what we passed as the first argument to the actual C-function.

Check to see that this all works. It worked for me. For completeness I will put the full Julia code below. Happy programming!

x = Array{Float64}(1)
y = Array{Float64}(1)
fpi = convert(Float64,pi)
xl = [0.; 0.; 0.]
xu = [fpi; fpi; fpi]
 
function integrand{T,T2,T3}(x::T,dim::T2,params::T3)
  A = 1.0 / (pi * pi * pi)
  return 3*A / (1.0 - cos(unsafe_load(x,1))*cos(unsafe_load(x,2))*cos(unsafe_load(x,3)))::Cdouble
end
 
integrand_c = cfunction(integrand,Cdouble,(Ptr{Cdouble},Ptr{Cdouble},Ptr{Cdouble}))
 
calls = 500000
mode = 3
dim = 3
ccall((:monte_carlo_integrate,"/home/crackauc/Public/libMonte.so"),Int32,(Ptr{Void},Ptr{Cdouble},Ptr{Cdouble},Int32,Int32,Ptr{Cdouble},Ptr{Cdouble},Csize_t),integrand_c,x,y,mode,dim,xl,xu,calls)
res=x[1]
err=y[1]

The post Using Julia’s C Interface to Utilize C Libraries appeared first on Stochastic Lifestyle.

A Million Text Files And A Single Laptop

By: randyzwitch - Articles

Re-posted from: http://randyzwitch.com/gnu-parallel-medium-data/

GNU Parallel Cat Unix

Wait…What? Why?

More often that I would like, I receive datasets where the data has only been partially cleaned, such as the picture on the right: hundreds, thousands…even millions of tiny files. Usually when this happens, the data all have the same format (such as having being generated by sensors or other memory-constrained devices).

The problem with data like this is that 1) it’s inconvenient to think about a dataset as a million individual pieces 2) the data in aggregate are too large to hold in RAM but 3) the data are small enough where using Hadoop or even a relational database seems like overkill.

Surprisingly, with judicious use of GNU Parallel, stream processing and a relatively modern computer, you can efficiently process annoying, “medium-sized” data as described above.

Data Generation

For this blog post, I used a combination of R and Python to generate the data: the “Groceries” dataset from the arules package for sampls ing transactions (with replacement), and the Python Faker (fake-factory) package to generate fake customer profiles and for creating the 1MM+ text files.

The contents of the data itself isn’t important for this blog post, but the data generation code is posted as a GitHub gist should you want to run these commands yourself.

Problem 1: Concatenating (cat * >> out.txt ?!)

The cat utility in Unix-y systems is familiar to most anyone who has ever opened up a Terminal window. Take some or all of the files in a folder, concatenate them together….one big file. But something funny happens once you get enough files…

$ cat * >> out.txt
-bash: /bin/cat: Argument list too long

That’s a fun thought…too many files for the computer to keep track of. As it turns out, many Unix tools will only accept about 10,000 arguments; the use of the asterisk in the `cat` command gets expanded before running, so the above statement passes 1,234,567 arguments to `cat` and you get an error message.

One (naive) solution would be to loop over every file (a completely serial operation):

for f in *; do cat "$f" >> ../transactions_cat/transactions.csv; done

Roughly 10,093 seconds later, you’ll have your concatenated file. Three hours is quite a coffee break…

Solution 1: GNU Parallel & Concatenation

Above, I mentioned that looping over each file gets you past the error condition of too many arguments, but it is a serial operation. If you look at your computer usage during that operation, you’ll likely see that only a fraction of a core of your computer’s CPU is being utilized. We can greatly improve that through the use of GNU Parallel:

ls | parallel -m -j $f "cat {} >> ../transactions_cat/transactions.csv"

The `$f` argument in the code is to highlight that you can choose the level of parallelism; however, you will not get infinitely linear scaling, as shown below (graph code, Julia):

Given that the graph represents a single run at each level of parallelism, it’s a bit difficult to say exactly where the parallelism gets maxed out, but at roughly 10 concurrent jobs, there’s no additional benefit. It’s also interesting to point out what the `-m` argument represents; by specifying `m`, you allow multiple arguments (i.e. multiple text files) to be passed as inputs into parallel. This alone leads to an 8x speedup over the naive loop solution.

Problem 2: Data > RAM

Now that we have a single file, we’ve removed the “one million files” cognitive dissonance, but now we have a second problem: at 19.93GB, the amount of data exceeds the RAM in my laptop (2014 MBP, 16GB of RAM). So in order to do analysis, either a bigger machine is needed or processing has to be done in a streaming or “chunked” manner (such as using the “chunksize” keyword in pandas).

But continuing on with our use of GNU Parallel, suppose we wanted to answer the following types of questions about our transactions data:

  1. How many unique products were sold?
  2. How many transactions were there per day?
  3. How many total items were sold per store, per month?

If it’s not clear from the list above, in all three questions there is an “embarrassingly parallel” portion of the computation. Let’s take a look at how to answer all three of these questions in a time- and RAM-efficient manner:

Q1: Unique Products

Given the format of the data file (transactions in a single column array), this question is the hardest to parallelize, but using a neat trick with the `tr` (transliterate) utility, we can map our data to one product per row as we stream over the file:

The trick here is that we swap the comma-delimited transactions with the newline character; the effect of this is taking a single transaction row and returning multiple rows, one for each product. Then we pass that down the line, eventually using `sort -u` to de-dup the list and `wc -l` to count the number of unique lines (i.e. products).

In a serial fashion, it takes quite some time to calculate the number of unique products. Incorporating GNU Parallel, just using the defaults, gives nearly a 4x speedup!

Q2. Transactions By Day

If the file format could be considered undesirable in question 1, for question 2 the format is perfect. Since each row represents a transaction, all we need to do is perform the equivalent of a SQL `Group By` on the date and sum the rows:

Using GNU Parallel starts to become complicated here, but you do get a 9x speed-up by calculating rows by date in chunks, then “reducing” again by calculating total rows by date (a trick I picked up at this blog post).

Q3. Total items Per store, Per month

For this example, it could be that my command-line fu is weak, but the serial method actually turns out to be the fastest. Of course, at a 14 minute run time, the real-time benefits to parallelization aren’t that great.

It may be possible that one of you out there knows how to do this correctly, but an interesting thing to note is that the serial version already uses 40-50% of the available CPU available. So parallelization might yield a 2x speedup, but seven minutes extra per run isn’t worth spending hours trying to the optimal settings.

But, I’ve got MULTIPLE files…

The three examples above showed that it’s possible to process datasets larger than RAM in a realistic amount of time using GNU Parallel. However, the examples also showed that working with Unix utilities can become complicated rather quickly. Shell scripts can help move beyond the “one-liner” syndrome, when the pipeline gets so long you lose track of the logic, but eventually problems are more easily solved using other tools.

The data that I generated at the beginning of this post represented two concepts: transactions and customers. Once you get to the point where you want to do joins, summarize by multiple columns, estimate models, etc., loading data into a database or an analytics environment like R or Python makes sense. But hopefully this post has shown that a laptop is capable of analyzing WAY more data than most people believe, using many tools written decades ago.

Julia iFEM3: Solving the Poisson Equation

By: Christopher Rackauckas

Re-posted from: http://www.stochasticlifestyle.com/julia-ifem3/

This is the third part in the series for building a finite element method solver in Julia. Last time we used our mesh generation tools to assemble the stiffness matrix. The details for what will be outlined here can be found in this document. I do not want to dwell too much on the actual code details since they are quite nicely spelled out there, so instead I will focus on the porting of the code. The full code will be available soon on a github repository, and so since most of it follows a straight translation from the linked document, I’ll leave it out of the post for you to find on the github.

The Ups, Downs, and Remedies to Math in Julia

At this point I have been coding in Julia for over a week and have been loving it. I come into each new function knowing that if I just change the array dereferencing from () to [] and wrap vec() calls around vectors being used as indexes (and maybe int()), I am about 95% done with porting a function. Then I usually play with cosmetic details. There are a few little details which make code in Julia a lot prettier. For example, for the FEM solver, we need to specify a function. In MATLAB, specifying such the function for which we want to solve -Delta u = f in-line would be done via anonymous functions like:

f = @(x)sin(2*pi.*x(:,1)).*cos(2*pi.*x(:,2));

I tend to have two problems with that code. For one, it’s not math, it’s programming, and so glancing at my equations and glancing at my code has a little bit of a translation step where errors can happen. Secondly, in many cases anonymous functions incur a huge performance decrease. This fact and the fact that MATLAB’s metaprogramming is restricted to string manipulation and eval destroyed a project I had tried a few years ago (general reaction-diffusion solver with a GUI, the GUI took in the reaction equations, but using anonymous functions killed the performance to where it was useless). However, in Julia functions can be defined inline and be first class, and have a nice appearance. For example, the same function in Julia is:

f(x) = sin(2π.*x[:,1]).*cos(2π.*x[:,2]);

Two major improvements here. For one, since the interpreter knows that variables cannot start with a number, it interprets 2π as the mathematical constant 2π. Secondly, yes, that’s a π! Julia uses allows unicode to be entered (In Juno you enter the latex pi and hit tab), and some of them are set to their appropriate mathematical constants. This is only cosmetic, but in the long-run I can see this as really beneficial for checking the implementation of equations.

However, not everything is rosy in Julia land. For one, many packages, including the FEM package I am working with, are in MATLAB. Luckily, the interfacing via MATLAB.jl tends to work really well. In the first post I showed how to do simple function calls. This did not work for what I needed to do since these function calls don’t know how to pass a function handle. However, digging into MATLAB.jl’s package I found out that I could do the following:

  put_variable(get_default_msession(),:node,node)
  put_variable(get_default_msession(),:elem,elem)
  put_variable(get_default_msession(),:u,u)
  eval_string(get_default_msession(),"sol = @(x)sin(2*pi.*x(:,1)).*cos(2*pi.*x(:,2))/(8*pi*pi);")
  eval_string(get_default_msession(),"Du = @(x)([cos(2*pi.*x(:,1)).*cos(2*pi.*x(:,2))./(4*pi) -sin(2*pi.*x(:,1)).*sin(2*pi.*x(:,2))./(4*pi)]);")
 
  eval_string(get_default_msession(),"h1 = getH1error(node,elem,Du,u);");
  eval_string(get_default_msession(),"l2 = getL2error(node,elem,sol,u);");
  h1 = jscalar(get_mvariable(get_default_msession(),:h1));
  l2 = jscalar(get_mvariable(get_default_msession(),:l2));

Here I send the variables node, elem, and u to MATLAB. Then I directly evaluate strings in MATLAB to make function handles. With all of the variables appropriately in MATLAB, I call the function getH1error and save its value (in MATLAB). I then use the get_mvariable to bring the result into MATLAB. That value is a value of MATLAB type, and so I use the MATLAB.jl’s conversion function jscalar to then get the scalar result h1. As you can see, using MATLAB.jl in this fashion is general enough to do any of your linking needs.

For very specialized packages, this is good. For testing the ported code for correctness, this is great. However, I hope not to do this in general. Sadly, every once in awhile I run into a missing function. In this example, I needed accumarray. It seems I am not the only MATLAB exile as once again Julia implementations are readily available. The lead Julia developer Stefan has a general answer:

function accumarray2(subs, val, fun=sum, fillval=0; sz=maximum(subs,1), issparse=false)
   counts = Dict()
   for i = 1:size(subs,1)
        counts[subs[i,:]]=[get(counts,subs[i,:],[]);val[i...]]
   end 
   A = fillval*ones(sz...) 
   for j = keys(counts)
        A[j...] = fun(counts[j])
   end
   issparse ? sparse(A) : A
end
  0.496260 seconds (2.94 M allocations: 123.156 MB, 8.01% gc time)
  0.536521 seconds (2.94 M allocations: 123.156 MB, 8.83% gc time)
  0.527007 seconds (2.94 M allocations: 123.156 MB, 9.41% gc time)
  0.544096 seconds (2.94 M allocations: 123.156 MB, 9.76% gc time)
  0.526110 seconds (2.94 M allocations: 123.156 MB, 12.22% gc time)

whereas Tim answer has less options but achieves better performance:

function accumarray(subs, val, sz=(maximum(subs),)) 
    A = zeros(eltype(val), sz...) 
    for i = 1:length(val) 
        @inbounds A[subs[i]] += val[i] 
    end 
    A 
end

Timings

  0.000355 seconds (10 allocations: 548.813 KB)
  0.000256 seconds (10 allocations: 548.813 KB)
  0.000556 seconds (10 allocations: 548.813 KB)
  0.000529 seconds (10 allocations: 548.813 KB)
  0.000536 seconds (10 allocations: 548.813 KB)
  0.000379 seconds (10 allocations: 548.813 KB)

Why is Julia “Missing” So Many Functions? And How Do We Fix It?

This is not the first MATLAB function I found myself missing. Off the top of my head I know I had to get/make versions of meshgrid, dot(var,dimension) just in the last week. To the dismay of many MATLAB exiles, many of the Julia developers are against “cluttering the base” with these types of functions. While it is easy to implement these routines yourself, many of these routines are simple and repeated by mathematical programmers around the world. By setting a standard name and implementation to the function, it helps code-reusability and interpretability.

However, the developers do make a good point that there is no reason for these functions to be in the Base. Julia’s Base is for functions that are required for general use and should be kept small in order to make it easier for the developers to focus on the core functionality and limit the resources required for a standard Julia install. This will increase the number of places where Julia could be used/adopted, and will help ensure the namespace isn’t too full (i.e. you’re not stepping on too many pre-made functions).

But mathematicians need these functions. That is why I will be starting a Julia Extended Mathematical Package. This package will be to hold the functions that are not essential language functions, but “essential math language” functions like you’d find in the base of MATLAB, R, numpy/scipy, etc., or even just really useful routines for mathematical programming. I plan on cleaning up the MATLAB implementations I have found/made ASAP and putting this package up on github for others to contribute to. My hope is to have a pretty strong package that contains the helper functions you’d expect to have in a mathematical programming language. Then just by typing using ExtendedMath, you will have access to all the special mathematical functionality you’re used to.

Conclusion

As of now I have a working FEM solver in Julia for Poisson’s equation with mixed Neumann and Dirichlet boundary conditions. This code has been tested for convergence and accuracy and is successful. However, this code has some calls to MATLAB. I hope to clean this up and after this portion is autonomous, I will open up the repository. The next stage will be to add more solvers: more equations, adaptive solvers, etc., as I go through the course. As, as mentioned before, I will be refactoring out the standard mathematical routines and putting that to a different library which I hope to get running ASAP for others to start contributing to. Stay tuned!

The post Julia iFEM3: Solving the Poisson Equation appeared first on Stochastic Lifestyle.