The Artima Developer Community
Sponsored Link

Weblogs Forum
Josh Bloch on the Semantic Gap

33 replies on 3 pages. Most recent reply: Oct 2, 2009 6:31 PM by Raoul Duke

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 33 replies on 3 pages [ « | 1 2 3 | » ]
Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 21, 2009 11:53 AM
Reply to this message Reply
Advertisement
It's very tempting to re-quote Cameron Purdy in particular after this "philosophical" discussion about hidden ( from what/whom? ) vs removed ( from where? ) complexity. I just want to note that those notions are not self-evident even if one finds a good proverb.

The whole discussion about performance models of programming languages seems to be quite apt to LtU. I remember computing time semantics being mentioned just recently in the context of a paper which didn't got enthusiastic reviews - but the discussion was interesting nevertheless:

http://lambda-the-ultimate.org/node/3332

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 21, 2009 10:21 PM
Reply to this message Reply
So basically, according to the wiki, we should avoid:

&& and ||, field access, polymorphism, division, and non-constant looping.

What is the point of using Java then? Why do we need a fancy VM? This seems a little silly to me.

Michael Chermside

Posts: 17
Nickname: mcherm
Registered: Jan, 2004

Re: Josh Bloch on the Semantic Gap Posted: Sep 21, 2009 10:43 PM
Reply to this message Reply
John, you write:

> In the domain of the real numbers, on the contrary,
> arithmetic is in fact complete (it is not possible to
> find theorems that are true but not provable).

Is that so? How interesting! Can you give me a reference where I can learn more?

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 1:27 AM
Reply to this message Reply
I missed Josh's talk but caught another one of his mini-rants on the topic.

I totally agree with Cliff Click: until you have profiler proof that something is a hot spot, implement it in the simplest, dog-slowest, most-easily-testable-ist way possible, semantic and all other gaps be damned.

At the conference people were sitting around worrying about 10% speed ups over the ordering of bytecode and hotspot tricks, when Cliff demonstrated a 30-f**king-X speedup via judicious use of the Azul profiler in code written by a pretty good developer.

There's your low hanging fruit. Who cares if you don't know what an operator costs? Given how complicated hardware is these days, who knows how expensive a memory load is? Or even what one is?

It doesn't matter. Tools, better, easier to use, empirical tools, do.

Cheers,
Carson

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 6:14 AM
Reply to this message Reply
> I missed Josh's talk but caught another one of his
> mini-rants on the topic.
>
> I totally agree with Cliff Click: until you have profiler
> proof that something is a hot spot, implement it in the
> simplest, dog-slowest, most-easily-testable-ist way
> possible, semantic and all other gaps be damned.
>
> At the conference people were sitting around worrying
> about 10% speed ups over the ordering of bytecode and
> hotspot tricks, when Cliff demonstrated a 30-f**king-X
> speedup via judicious use of the Azul profiler in code
> written by a pretty good developer.
>
> There's your low hanging fruit. Who cares if you don't
> know what an operator costs? Given how complicated
> hardware is these days, who knows how expensive a memory
> load is? Or even what one is?
>
> It doesn't matter. Tools, better, easier to use,
> empirical tools, do.
>
> Cheers,
> Carson

While what you say has merit, what if changing the source code after the profiling means to throw out the current design and start from scratch?

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 6:31 AM
Reply to this message Reply
> There's your low hanging fruit. Who cares if you don't
> know what an operator costs? Given how complicated
> hardware is these days, who knows how expensive a memory
> load is? Or even what one is?
>
> It doesn't matter. Tools, better, easier to use,
> empirical tools, do.

First when identifying the problem code you have to be careful that your tool doesn't change it. Unfortunately attempting to profile a system all too often affects the system.

Then when you know where the problem is you may still need some sort of mental model of how computation is performed to design a better implementation. If your hot code is multiplying large matrices, you won't get a first class solution if your model does not include the effect of processor cache. If you ignore the cache, performance will fall off a cliff somewhere between 100x100 and 1000x1000 on common processors.

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 1:13 PM
Reply to this message Reply
> While what you say has merit, what if changing the source
> code after the profiling means to throw out the current
> design and start from scratch?

Well, life is hard and we all have our crosses to bear. We were probably going to throw the code out anyway, since we most likely didn't listen to our customers and no doubt we went down some "creative" rat holes, being as clever as we are.

You can always make a guess at the start as to what sort of macroscopic performance architecture you might need, and those guesses can pan out (or lead to disaster if they interfere too much with day-to-day programming) but worrying about a semantic cap at the operator/function level is just navel gazing.

Worse is better,
Carson

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 1:20 PM
Reply to this message Reply
> Then when you know where the problem is you may still need
> some sort of mental model of how computation is performed
> to design a better implementation. If your hot code is
> multiplying large matrices, you won't get a first class
> solution if your model does not include the effect of
> processor cache. If you ignore the cache, performance will
> fall off a cliff somewhere between 100x100 and 1000x1000
> on common processors.

If you are multiplying matrices, and perf matters to you, you should be using a library.

Most guys are banging out web apps, web services, transaction processing systems, etc. And most people multiplying matrices are eventually hitting a disk or network somewhere that totally destroys whatever speedup they achieved via a finely tuned library.

The semantic gap is an effin' canyon, and it doesn't matter. Architectural considerations dominate, and it's almost always a rewrite anyway. Tools, tools, tools.

Cheers,
Carson

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 2:11 PM
Reply to this message Reply
> If you are multiplying matrices, and perf matters to you,
> you should be using a library.
As a mathematician implementing algorithms is part of my job, after all somebody has to write those libraries.

>
> Most guys are banging out web apps, web services,
> transaction processing systems, etc.
Very likely, but it isn't my world.

>And most people
> e multiplying matrices are eventually hitting a disk or
> network somewhere that totally destroys whatever speedup
> they achieved via a finely tuned library.
For me it is normal to have processes that run for (many) minutes at 100% CPU utilization with a few seconds of I/O at either end. Many people working in mathematics, hard sciences (physics, chemistry, etc) or engineering will have processing tasks of a similar nature.

>
> The semantic gap is an effin' canyon, and it doesn't
> matter.
It doesn't matter to you.

Mark.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 2:41 PM
Reply to this message Reply
> > If you are multiplying matrices, and perf matters to
> you,
> > you should be using a library.
> As a mathematician implementing algorithms is part of my
> job, after all somebody has to write those libraries.

I'm going to need to see you your license to think, sir.

For most Java developers, the biggest performance gains are going to come from macro level improvements. I've seen a lot of cases where people spent many days trying to optimize a search routine when a much easier change to the application architecture produced gains far greater than what would be achieved if the search were absolutely optimal. (i.e. eliminate the need for the search entirely.)

For the kinds of case you are referring to, I can see why this kind of knowledge is important. But wouldn't a native implementation be a better choice? Is the rationale for doing this in Java to avoid headaches related to using native libraries in Java or something else?

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 2:58 PM
Reply to this message Reply
> For the kinds of case you are referring to, I can see why
> this kind of knowledge is important. But wouldn't a
> native implementation be a better choice? Is the
> rationale for doing this in Java to avoid headaches
> related to using native libraries in Java or something
> else?
Although my code is responsible for most of the CPU use, in terms of lines of code it is a relatively small portion of the overall product. Many years ago the computational section was implemented in a different language (Fortran) to the GUI and user level components (C++ at that time). The resulting barrier between the two sides of the system was very unpleasant. Most developers were only competent on one side of the line. All bugs were caused by something in the here be dragons code on the other side (not really true, but it is human nature to behave that way).
So we resolved to find a single language in which the entire system could be implemented. In practice it took quite a long time to eliminate all of the 'native' code. While there probably is a modest performance hit, I don't worry about and instead spend my time finding the fastest way to implement the required algorithms in Java.

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 3:09 PM
Reply to this message Reply
> As a mathematician implementing algorithms is part of my
> job, after all somebody has to write those libraries.

Sure, but you guys are smart. You can figure this stuff out on your own.

> > Most guys are banging out web apps, web services,
> > transaction processing systems, etc.
> Very likely, but it isn't my world.

No argument here.

> For me it is normal to have processes that run for (many)
> minutes at 100% CPU utilization with a few seconds of I/O
> at either end. Many people working in mathematics, hard
> sciences (physics, chemistry, etc) or engineering will
> have processing tasks of a similar nature.

Right. An then you ponder over the data for... hours? Days? Months?

I'm not saying the speed up isn't important, but even for many scientific computations we are getting to the point where the computations that take too long are just non-polynomial or non-converging.

> > The semantic gap is an effin' canyon, and it doesn't
> > matter.
> It doesn't matter to you.

I don't think it matter to most people, and if we concentrate on it to the detriment of other possible focuses, we'd be hurting the overall art. Better tools are going to help most developers, even most scientific developers, more than on-the-rails semantic gap minding.

Cheers,
Carson

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 3:44 PM
Reply to this message Reply
> Right. An then you ponder over the data for... hours?
> Days? Months?
>

Often the data is complete around 4pm, the finished result (after some manual checking and adjustment) is required by 5pm. In most cases the maximum acceptable computation time is around 15 minutes (because you might have to run it again).

Joshua Bloch

Posts: 2
Nickname: jbloch
Registered: Dec, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 22, 2009 5:16 PM
Reply to this message Reply
A few clarifications:

Remember that this discussion took place at a JVM workshop. I was not saying that the semantic gap is a terrible problem for typical programmers, but it is a very real problem for library designers, language designers, VM implementers, and the like.

James Watson said:

"So basically, according to the wiki, we should avoid:

&& and ||, field access, polymorphism, division, and non-constant looping.

What is the point of using Java then? Why do we need a fancy VM? This seems a little silly to me."


I would never suggest that you should avoid all of these things! First and foremost, you should write short, clear, maintainable, correct programs. Then optimize as necessary (if at all). That was one of my main messages in Effective Java (see, e.g., Item 55 "Optimize Judiciously"). My opinion hasn't changed.

But when it does come time to optimize, the process is greatly complicated by the semantic gap. Consider this: Suppose you carefully write a well-designed microbenchmark that does everything right (e.g., warms up the VM, ensures that computation is not optimized away, times a sufficient amount of computation, does multiple timings to ensure repeatability). You run the benchmark, and see that after warmup, every run takes nearly the same amount of time. Happiness? You run the benchmark again, and again every run takes the same amount of time, but it's a different amount! You run the program twenty times, and see the results clustering into several groups, but always consistent within a program-run. What is going on?

In modern VMs such as HotSpot, the task of deciding what to inline and when to inline it is performed by a background thread (at runtime). This process is called "compilation planning." Because it's multithreaded, it's nondeterministic. Suppose you have code that looks something like this:
    static void foo(int m, int n) {
        for (int i = 0; i < m; i++)
            bar(n);
    }
 
    static void bar(int n)  {
        for (int i = 0; i < n; i++)
            baz();
    }

The compilation planning thread uses "inlining heuristics" to decide what to inline. It has to make decisions based on local information, but they have global effects. In the simplified example above, inlining the call to bar may preclude inlining the call to baz, and vice-versa. Of course you're far better off only inlining the call to baz (in the inner loop), but the compilation planning thread doesn't have the global knowledge to make the right decision, so you may end up doing the right inlining some of the time and the wrong one some of the time. This explains the confusing behavior we observed above: when you benchmark the code, you get consistency from run to run in a single program-run (after the VM is "warmed up"), but restart the VM and you get a different consistent result.

For more information on this topic, see Georges, Buytaert and Eeckhout's OOPSLA 2007 paper, Statistically Rigorous Java Performance Evaluation: http://itkovian.net/base/files/papers/oopsla2007-georges-preprint.pdf .

This is one of many such example of the poor performance model that we live with these days. Mytkowicz and Diwan presented a paper at ASPLOS '09 discussing the problem from a more C/C++/Unix-centric (and philosophical) point-of-view. The paper is entitled Producing Wrong Data Without Doing Anything Obviously Wrong!: http://www-plan.cs.colorado.edu/diwan/asplos09.pdf.

Even if you write only X86 assembly code, the performance model is fiendishly complex. Cliff Click gives a talk on this from a processor-design perspective, entitled This Is Not Your Father's Von Neumann Machine; How Modern Architecture Impacts Your Java Apps: http://www.azulsystems.com/events/javaone_2009/session/2009_J1_HardwareCrashCourse.pdf .

A part of the problem is due to the underlying memory system. This issue is explored by Ulrich Drepper's 2007 paper, What Every Programmer Should Know About Memory: http://people.redhat.com/drepper/cpumemory.pdf .

Finally, Doug Lea, David Bacon, and David Grove presented a paper at the 2008 SIGPLAN Workshop on Programming Language Curriculum discussing these issues from a teaching standpoint: http://gee.cs.oswego.edu/dl/papers/LeaBaconGrove.pdf , http://portal.acm.org/citation.cfm?id=1480848 .

That's five papers in the last couple of years, and there are others. So why is this such a hot topic all of a sudden? Because it's effecting everyone who is trying to do serious performance work these days. It is much more difficult to optimize code than it used to be, and the optimized code is much less likely to remain "optimal" as VMs, processors, and other infrastructure evolve.

In summary, I agree that this topic is not terribly important to typical application programmers in their daily work, and should never be used as an excuse for premature optimization. But it is crucially important to people who build infrastructure and do performance analysis.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Josh Bloch on the Semantic Gap Posted: Sep 23, 2009 9:17 AM
Reply to this message Reply
> In summary, I agree that this topic is not terribly
> important to typical application programmers in their
> daily work, and should never be used as an excuse
> for premature optimization. But it is crucially important
> to people who build infrastructure and do performance
> analysis.

I was playing the fool a bit but I didn't see much on that wiki page explaining where this knowledge should be considered. The problem with this kind of information without context is that people will start prematurely optimizing things. A perfect example of this is how often I see code where developers use StringBuffer to build constant strings and simple one-line string concatenations.

Flat View: This topic has 33 replies on 3 pages [ « | 1  2  3 | » ]
Topic: Speaking At Developer Day in Boulder Previous Topic   Next Topic Topic: Managing Records in Python (Part 1 of 3)


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us