Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #15504 > unrolled thread

Dealing with higher order operations coupled with primitives

Back to article view | Back to comp.lang.java.programmer

Contents

  Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-21 22:08 -0500
    Re: Dealing with higher order operations coupled with primitives Gina Engli <gengli239777@gmail.com> - 2012-06-21 23:17 -0400
      Re: Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-22 15:13 -0500
    Re: Dealing with higher order operations coupled with primitives markspace <-@.> - 2012-06-21 21:32 -0700
      Re: Dealing with higher order operations coupled with primitives Gina Engli <gengli239777@gmail.com> - 2012-06-22 02:31 -0400
        Re: Dealing with higher order operations coupled with primitives Fred Greer <fggreer@nospam.invalid> - 2012-06-22 06:36 +0000
          Re: Dealing with higher order operations coupled with primitives Gina Engli <gengli239777@gmail.com> - 2012-06-22 02:43 -0400
            Re: Dealing with higher order operations coupled with primitives Lew <lewbloch@gmail.com> - 2012-06-22 12:45 -0700
              Re: Dealing with higher order operations coupled with primitives Sixteen of Seventeen <sseventeen@gmail.com> - 2012-06-22 18:24 -0400
                Re: Dealing with higher order operations coupled with primitives Lew <noone@lewscanon.com> - 2012-06-22 19:59 -0700
                  Re: Dealing with higher order operations coupled with primitives Sixteen of Seventeen <sseventeen@gmail.com> - 2012-06-22 23:16 -0400
                    Re: Dealing with higher order operations coupled with primitives Lew <noone@lewscanon.com> - 2012-06-22 22:13 -0700
                      Re: Dealing with higher order operations coupled with primitives Borg Queen <queen@unimatrix.zero> - 2012-06-23 01:18 -0400
                        Re: Dealing with higher order operations coupled with primitives Lew <noone@lewscanon.com> - 2012-06-23 07:59 -0700
                          Re: Dealing with higher order operations coupled with primitives Borg Queen <queen@unimatrix.zero> - 2012-06-23 12:12 -0400
      Re: Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-22 15:28 -0500
        Re: Dealing with higher order operations coupled with primitives Gina Engli <gengli239777@gmail.com> - 2012-06-22 18:25 -0400
    Re: Dealing with higher order operations coupled with primitives Roedy Green <see_website@mindprod.com.invalid> - 2012-06-22 00:33 -0700
      Re: Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-22 15:31 -0500
    Re: Dealing with higher order operations coupled with primitives rossum <rossum48@coldmail.com> - 2012-06-22 13:00 +0100
      Re: Dealing with higher order operations coupled with primitives markspace <-@.> - 2012-06-22 07:45 -0700
        Re: Dealing with higher order operations coupled with primitives Lew <lewbloch@gmail.com> - 2012-06-22 12:45 -0700
          Re: Dealing with higher order operations coupled with primitives markspace <-@.> - 2012-06-22 13:34 -0700
            Re: Dealing with higher order operations coupled with primitives Lew <noone@lewscanon.com> - 2012-06-22 20:04 -0700
      Re: Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-22 15:22 -0500
        Re: Dealing with higher order operations coupled with primitives Lew <lewbloch@gmail.com> - 2012-06-22 14:27 -0700
    Re: Dealing with higher order operations coupled with primitives "Aaron W. Hsu" <arcfide@sacrideo.us> - 2012-06-22 15:14 -0500

Page 1 of 2  [1] 2  Next page →

#15504 — Dealing with higher order operations coupled with primitives

My inexperience with Java has got me into a bit of a funk, both in terms 
of its static typing system and in terms of Objects for higher-order 
programming.

To give a simplified example of what I am dealing with, I want to have an 
class that stores data in arrays of primitives (since I do not want to 
incur the boxing overhead of Objects), but I also want to have multiple 
types. I seem to have two options. I can subclass the main object to 
specialize to a type, or I can use an internal type field that indicates 
the type of the object. I have tried it both ways, and both seem to be 
annoying. It does not seem that I can use Generics with primitive types, 
so that also seems out.  Is there a better way?

Either way, I am finding it annoying to program because I want to have an 
abstraction for functions that operate over this structure. So I might 
have a class as follows:

public abstract class Function {

public abstract void apply(Data result, Data argument);

}

Now, this works in the general case pretty well. I have a few constraint:

1) I want to make sure the interface has as low an overhead as possible;
2) I want to make sure that the interface allows me to reduce allocations 
as much as possible.

I am using the result argument instead of returning a newly allocated 
Data instance because of #1. Specifically, I might have something like:

public void apply(Data result, Data arg) {
  res.fun1(arg);
  res.fun2();
  res.fun3();
}

Where I can reuse the already allocated, potentially very large internal 
primitive data structure in res multiple times, including across function 
applications, instead of requiring a copy of that large structure (these 
structures could, for instance, be gigabyte arrays). 

Of course, the reason that I am using Function is that I want to be able 
to define certain methods that take functions. For example, a form of 
map, say:

void map(Function fun, Data arg)

Here if there are many parts to arg, I may fun.apply(tmp, arg.get(...)) 
many many times. In my benchmarks, this seems to be much slower than what 
I could get without this abstraction.  I am trying to reduce this 
overhead as much as possible.

One attempt I have made with this is to have an FunctionPrimitive 
interface.  This interface provides apply methods whose arguments are 
primitives, rather than Data elements. This means that I do not have to 
incur the overhead of applying on intermediate or temporary Data elements 
that I have to get rid of again sometime later.  It's the unboxing and 
boxing issue again.  Doing this actually nets me some pretty big wins, 
but it's still too much overhead. 

Part of it is the dynamic checking that I have to do with each function 
to ensure that I have the right type all of the time, but I am not sure 
what other things may be happening. For example, I do not want my 
FunctionPrimitive interface to have something like:

Data apply(int arg)

Because this requires creating an intermediate Data element that I will 
just destroy later on.  This is slightly better:

void apply(Data result, int arg)

But it still requires creating at least one temporary and then copying 
out of it each time I invoke apply(). It also means that I cannot use the 
subclassing of Data approach that I mentioned above because I cannot know 
ahead of time, and therefore cannot preallocate the result Data object 
before calling apply. This almost seems to necessitate a private type 
field in Data. Then I can have some setter:

void set(int)
void set(boolean)

and so forth, which do the right things based on their input, and that 
the apply() method will use to set the elements in the result object.

But I want to do better than that. If there is some sort of information, 
maybe and index or key, that I can provide:

void apply(Data result, Key idx, int arg)

Then I can actually pass the Data object that is going to be used 
eventually to the apply method and just have it put in the right data. 

Even with all of this, though, in a simple benchmark, this abstraction 
stuff still makes me about five times slower (2 versus less than 10 
seconds). I really want to cut this overhead down.

Can someone suggest how I might improve my design? As a simple real life 
instance, say I want to apply a function:

f(0) = 0
f(n) = n + f(n-1)

I want to apply this function over the numbers in the range [0,n) and 
then print the last one, just for verification.

The simple, naive Java might look like this, I suppose:

public class IotaSumReduce {

  public static int sum(int n) {
    int res = 0;
    for (int i = 0; i < n; i++) res += i;
  }

  public static void main(String[] args) {
    int count = 100000;
    int[] res = new int[count];
    
    for (int i = 0; i < count; i++) res[i] = sum(i);
    System.out.println(res[count - 1]);
  }
}

Now, let's say that I want to map this to something a little crazier, 
say, a functional style.  A not so efficient version:

(car (reverse (map (lambda (n) (fold-left + 0 (iota n))) (iota 100000))))

But we can go crazier, let's do APL, which is nearly a copy of the above 
in approach:

⊃⌽{+/⍳⍵}¨⍳100000

Now, in my benchmarks, the APL version above actually runs reasonably 
quickly for being interpreted: about four seconds, give or take. The Java 
version runs in about 1.7 seconds, the C version on O2, about 3 seconds. 
So, all of these are reasonably close at this point. However, let's say 
that I wanted to take that functional APL style program and try to use my 
above approach.

public class AplIotaSumReduce {
  
  private static class Sum extends Function {
    void apply(AplArray res, AplArray arg) {
      Function plus = new AplArray.PlusFunction();
      res.iota(arg);
      res.reduce(plus, res);
    }
  }

  public static void main(String[] args) {
    AplArray res = new AplArray();
    Function sum = new Sum();

    res.iota(100000);
    res.each(sum, res);
    System.out.println(res.getInt(99999);
  }
}

This program runs much much slower for me.  If Function plus is used, 
then we are talking about minutes, and not seconds.  If I use the 
FunctionPrimitive optimization I talk about above, I can get that down to 
around 9 - 10 seconds. That's much better, but that's still not good 
enough, I really need to get into the range of the naive C, APL, or Java 
programs. I am wondering what re-engineering might allow me to get there? 
I would appreciate any pointers that you all may have. And sorry for the 
other languages, like Scheme and APL, they are just fun examples to use, 
as they illustrate the higher-order paradigm I am trying to achieve, and 
they have a succinct mapping to this model I am playing with.

-- 
Aaron W. Hsu | arcfide@sacrideo.us | http://www.sacrideo.us
Programming is just another word for the lost art of thinking.

[toc] | [next] | [standalone]

#15505

Wouldn't it be easier to just use Clojure for the higher-order stuff, 
and its map, reduce, etc. or amap, areduce, etc.?

[toc] | [prev] | [next] | [standalone]

#15525

On Thu, 21 Jun 2012 23:17:39 -0400, Gina Engli wrote:

> Wouldn't it be easier to just use Clojure for the higher-order stuff,
> and its map, reduce, etc. or amap, areduce, etc.?

It would be "easier" to code this up in a number of languages, but I 
am trying to build a core runtime for a compiler that will compile 
either to Java or to JVM, either one of which, it seems, I will need 
the core language primitives to be defined somehow, and right now 
the fastest version of the runtime that I have implemented is in 
Java; things like Scala and the like have not been as fast.

-- 
Aaron W. Hsu | arcfide@sacrideo.us | http://www.sacrideo.us
Programming is just another word for the lost art of thinking.

[toc] | [prev] | [next] | [standalone]

#15508

On 6/21/2012 8:08 PM, Aaron W. Hsu wrote:

> public class IotaSumReduce {
>
>    public static int sum(int n) {
>      int res = 0;
>      for (int i = 0; i < n; i++) res += i;
        return res;
>    }


This method needed a return value; I assume you meant res.


> public class AplIotaSumReduce {
>
>    private static class Sum extends Function {
>      void apply(AplArray res, AplArray arg) {
>        Function plus = new AplArray.PlusFunction();


I think we are going to need the definitions of Function, AplArray, 
AplArray.PlusFunction, etc.  I'd prefer not to guess how you are 
implementing these right now.


>        res.iota(arg);
>        res.reduce(plus, res);

I think I understand reduction, but shouldn't it return a value?  I 
don't see how you reduce in-place like this;  are you over-writing the 
0th element or something?


>
> This program runs much much slower for me.


We'll definitely need more code.  We're far afield of what Java normally 
does.  Trying to guess at your implementation is counter productive, and 
standard ways of doing this don't exist afaik, as Java programmers don't 
normally (ever?) do this sort of thing.

I'll agree with others: Haskell/Clojure seem a better fit.

[toc] | [prev] | [next] | [standalone]

#15510

On 22/06/2012 12:32 AM, markspace wrote:
> I'll agree with others: Haskell/Clojure seem a better fit.

If the OP specifically wants to run on the JVM (to run in a servlet 
container, for instance, or to gain WORA easily) or have access to 
Java's large and useful standard library, Clojure, in particular, has 
the advantage of being JVM-hosted and providing said access.

[toc] | [prev] | [next] | [standalone]

#15511

On Fri, 22 Jun 2012 02:31:54 -0400, Gina Engli wrote:

> On 22/06/2012 12:32 AM, markspace wrote:
>> I'll agree with others: Haskell/Clojure seem a better fit.
> 
> If the OP specifically wants to run on the JVM (to run in a servlet
> container, for instance, or to gain WORA easily) or have access to
> Java's large and useful standard library, Clojure, in particular, has
> the advantage of being JVM-hosted and providing said access.

Also if he prefers to code in Java, as he can code the really functional 
stuff in Clojure and the rest in Java since the two can be made to 
interoperate easily.

[toc] | [prev] | [next] | [standalone]

#15512

On 22/06/2012 2:36 AM, Fred Greer wrote:
> On Fri, 22 Jun 2012 02:31:54 -0400, Gina Engli wrote:
>
>> On 22/06/2012 12:32 AM, markspace wrote:
>>> I'll agree with others: Haskell/Clojure seem a better fit.
>>
>> If the OP specifically wants to run on the JVM (to run in a servlet
>> container, for instance, or to gain WORA easily) or have access to
>> Java's large and useful standard library, Clojure, in particular, has
>> the advantage of being JVM-hosted and providing said access.
>
> Also if he prefers to code in Java, as he can code the really functional
> stuff in Clojure and the rest in Java since the two can be made to
> interoperate easily.

Yes, but why the hell would anyone prefer to code in Java? ;)

[toc] | [prev] | [next] | [standalone]

#15521

Gina Engli wrote:
> Yes, but why the hell would anyone prefer to code in Java? ;)

Because it's the best friggin' programming language ever invented
or that ever will be!

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15532

On 22/06/2012 3:45 PM, Lew wrote:
> Gina Engli wrote:
>> Yes, but why the hell would anyone prefer to code in Java? ;)
>
> Because it's the best friggin' programming language ever invented
> or that ever will be!

Classic unsubstantiated and erroneous claim.

[toc] | [prev] | [next] | [standalone]

#15536

Sixteen of Seventeen wrote:
> Lew wrote:
>> Gina Engli wrote:
>>> Yes, but why the hell would anyone prefer to code in Java? ;)
>>
>> Because it's the best friggin' programming language ever invented
>> or that ever will be!
>
> Classic unsubstantiated and erroneous claim.

You don't know a joke when you see one. Quit parroting your nonsense.

It was a joke, right? Get it?

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

[toc] | [prev] | [next] | [standalone]

#15538

On 22/06/2012 10:59 PM, Lew wrote:
> Sixteen of Seventeen wrote:
>> Lew wrote:
>>> Gina Engli wrote:
>>>> Yes, but why the hell would anyone prefer to code in Java? ;)
>>>
>>> Because it's the best friggin' programming language ever invented
>>> or that ever will be!
>>
>> Classic unsubstantiated and erroneous claim.
>
> You don't know a joke when you see one.

What does your classic unsubstantiated and erroneous claim have to do 
with Java, Lew?

> Quit parroting your nonsense.

What does your classic erroneous presupposition have to do with Java, Lew?

> It was a joke, right? Get it?

What do your questions have to do with Java, Lew?

[toc] | [prev] | [next] | [standalone]

#15540

On 06/22/2012 08:16 PM, Sixteen of Seventeen wrote:
> What does your classic unsubstantiated and erroneous claim have to do with
> Java, Lew?

Plonk.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

[toc] | [prev] | [next] | [standalone]

#15541

On 23/06/2012 1:13 AM, Lew wrote:
> On 06/22/2012 08:16 PM, Sixteen of Seventeen wrote:
>> What does your classic unsubstantiated and erroneous claim have to do
>> with
>> Java, Lew?
>
> Plonk.

Killfiles are irrelevant. You will be assimilated. Resistance is futile.

[toc] | [prev] | [next] | [standalone]

#15546

Borg Queen wrote:
> Lew wrote:
>> Sixteen of Seventeen wrote:
>>> What does your classic unsubstantiated and erroneous claim have to do
>>> with
>>> Java, Lew?
>>
>> Plonk.
>
> Killfiles are irrelevant. You will be assimilated. Resistance is futile.

What does your classic unsubstantiated and erroneous claim have to do with Java?

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

[toc] | [prev] | [next] | [standalone]

#15548

On 23/06/2012 10:59 AM, Lew wrote:
> Borg Queen wrote:
>> Lew wrote:
>>> Sixteen of Seventeen wrote:
>>>> What does your classic unsubstantiated and erroneous claim have to do
>>>> with Java, Lew?
>>>
>>> Plonk.
>>
>> Killfiles are irrelevant. You will be assimilated. Resistance is futile.
>
> What does your classic unsubstantiated and erroneous claim have to do
> with Java?

Classic erroneous presupposition that my claim was either erroneous or 
unsubstantiated.

[toc] | [prev] | [next] | [standalone]

#15528

Thank you for the detailed reply...

On Thu, 21 Jun 2012 21:32:04 -0700, markspace wrote:
> 
> I think we are going to need the definitions of Function, AplArray,
> AplArray.PlusFunction, etc.  I'd prefer not to guess how you are
> implementing these right now.

Understandable.  I am preparing a complete set of examples today.

>>        res.iota(arg);
>>        res.reduce(plus, res);
> 
> I think I understand reduction, but shouldn't it return a value?  I
> don't see how you reduce in-place like this;  are you over-writing the
> 0th element or something?

It is able to reduce in place by swapping out the underlying array that 
contains the main elements with another single element one, but keeping 
the original set of elements around until it is done. 

The point of this style instead of having something that returns a new 
object is to allow for the composition of a number of these operations 
that can do the in-place updates, such as a series of arithmetic operations.
In this case, there is no need to allocate a large array for each operation. 

> We'll definitely need more code.  We're far afield of what Java normally
> does.  Trying to guess at your implementation is counter productive, and
> standard ways of doing this don't exist afaik, as Java programmers don't
> normally (ever?) do this sort of thing.

I am setting up a series of examples that will hopefully make things 
clearer.  I have considered Haskell and Clojure, but what I am after is a 
mature platform on which to construct a core runtime that will be used 
by my compiler's output. Haskell does not fit the bill as its behavior is 
too unpredictable, and Clojure still seems slower than Java, and less 
general in allowing me to play games with mutation.

-- 
Aaron W. Hsu | arcfide@sacrideo.us | http://www.sacrideo.us
Programming is just another word for the lost art of thinking.

[toc] | [prev] | [next] | [standalone]

#15533

On 22/06/2012 4:28 PM, Aaron W. Hsu wrote:
> I am setting up a series of examples that will hopefully make things
> clearer.  I have considered Haskell and Clojure, but what I am after is a
> mature platform on which to construct a core runtime that will be used
> by my compiler's output. Haskell does not fit the bill as its behavior is
> too unpredictable, and Clojure still seems slower than Java, and less
> general in allowing me to play games with mutation.

As I understand it, your use of mutation is with Java arrays. Clojure 
gives you access to Java arrays, including mutation, and with type hints 
the array operations should be as fast as in Java.

[toc] | [prev] | [next] | [standalone]

#15513

On Thu, 21 Jun 2012 22:08:37 -0500, "Aaron W. Hsu"
<arcfide@sacrideo.us> wrote, quoted or indirectly quoted someone who
said :

>To give a simplified example of what I am dealing with, I want to have an 
>class that stores data in arrays of primitives (since I do not want to 
>incur the boxing overhead of Objects),

Elements in arrays of primitives must all be of the same type.  If you
want to mix, you need arrays of Objects.

You can of course have subclasses of Objects each with a different
type of primitive array.
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
If you look in a computer programmer's freezer you will find all 
kinds of containers, but none of them labeled.  They do the same thing 
creating files without labeling the encoding.  You are just supposed to 
know.  Ditto with the MIME type, the separator and comment delimiters and 
column names in CSV files.  Ditto with the endian convention.  Imagine how 
much more civilised life would have been if Martha Stewart were the first 
programmer. 

[toc] | [prev] | [next] | [standalone]

#15529

On Fri, 22 Jun 2012 00:33:10 -0700, Roedy Green wrote:

> Elements in arrays of primitives must all be of the same type.  If you
> want to mix, you need arrays of Objects.
> 
> You can of course have subclasses of Objects each with a different type
> of primitive array.

Thank you for the reply.  At this point I am fine with not mixing element 
types and I understand that I will need Objects if I want to do that. On 
the other hand, there seem to be two approaches that I can take to 
doing the primitive arrays of different types, subclassing is one option. 
My original post outlines the troubles I had when I took this approach 
at first, and I would love it if you had a solution to my Function 
abstraction that allowed for this sort of subclassing.

Otherwise, I will post more information later today, I hope, that will 
clarify my attempts thus far.

-- 
Aaron W. Hsu | arcfide@sacrideo.us | http://www.sacrideo.us
Programming is just another word for the lost art of thinking.

[toc] | [prev] | [next] | [standalone]

#15514

On Thu, 21 Jun 2012 22:08:37 -0500, "Aaron W. Hsu"
<arcfide@sacrideo.us> wrote:

>(since I do not want to incur the boxing overhead of Objects)
Why not?  Have you tested how fast your program runs when you use
generics/boxing?

By all means eleminate boxing if you boxing program runs too slowly,
but until you have written it, tested it and profiled it to show that
boxing is the problem then you have no reason to avoid boxing.

rossum

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web