the perils of inlining

637 views
Skip to first unread message

Jason Zaugg

unread,
Jan 14, 2013, 11:03:31 AM1/14/13
to scala-i...@googlegroups.com
I've been taking a look at SI-6789 (partly because it has a cool ticket number...).

In a nutshell, inlining can change program semantics when code steps outside the type system and starts reflecting on the call stack. The example of the ticket was Class.forName, which indirectly calls `Reflection.getCallerClass(3)` on the way to finding out the callers classloader. In a pathalogical case, the inlining call to `Class.forName` could fail due to some classloader separation.

This trick is also used widely to implement security when one calls to SecurityManager.checkPermission. AFAICS, this is worse, as it looks not only at the immediatly enclosing caller, but all the way up the stack.

I've done some grepping of the JDK sources and compiled a list of code that isn't safe to inline (based only on the usage of `getCaller.*`, we can't sensibly do anything about indirect SecurityManager usage other than to let folks disable inlining).

We end up with:

  https://github.com/retronym/scala/compare/scala:2.10.x...retronym:ticket/6789 

Anyway, this was a bigger can of worms than I thought, and I'm not sure what to do with this.

Do we admit an admittedly partial list of 'unsafe to inline` methods like this? Does it give a false sense  of secuity? Does this problem actually come up in practice? How many folks (other than ourselves) are actually compiling with -optimize?

-jason

Erik Osheim

unread,
Jan 14, 2013, 11:12:23 AM1/14/13
to scala-i...@googlegroups.com
On Mon, Jan 14, 2013 at 05:03:31PM +0100, Jason Zaugg wrote:
> This trick is also used widely to implement security when one calls to
> SecurityManager.checkPermission. AFAICS, this is worse, as it looks not
> only at the immediatly enclosing caller, but all the way up the stack.

...

> Do we admit an admittedly partial list of 'unsafe to inline` methods like
> this? Does it give a false sense of secuity? Does this problem actually
> come up in practice? How many folks (other than ourselves) are actually
> compiling with -optimize?

I use -optimize a lot and haven't seen any issues with this yet. I'm
not really doing anything fancy with reflection or class loaders
though, so I don't think I would be directly affected by this one way
or the other.

I'm indifferent to the change. Inlining presupposes being willing to
change the call stack/context certain code will run in. So code that
wants to completely understand and control the entire call stack (e.g.
your security manager example) is clearly not compatible with the
general goals of inlining/-optimize.

If other people think this patch would help I'm not against it.

-- Erik

Simon Ochsenreither

unread,
Jan 14, 2013, 11:31:04 AM1/14/13
to scala-i...@googlegroups.com

Do we admit an admittedly partial list of 'unsafe to inline` methods like this? Does it give a false sense  of secuity? Does this problem actually come up in practice? How many folks (other than ourselves) are actually compiling with -optimize?

Well, if we are prepared to handle an ever-expanding list of methods and classes (as the last few dozen Java exploits have shown) ... let's go for it.

You already prohibit 2 of 3 reflection APIs which is a good thing, but you should probably also consider adding javax.lang.model, as they plan to add a runtime implementation in the future (by the way, does this sound familiar :-D) and who knows how they manage to mess it up this time.

Additionally, I would ban every package related to management beans, instrumentation, other language implementations (like _both_ JavaScript implementations) and RMI.

What about stuff related to sun.misc.Unsafe, btw?

Maybe a white-list would make more sense? :-D

Thanks and bye,

Simon

Jason Zaugg

unread,
Jan 14, 2013, 11:33:53 AM1/14/13
to scala-i...@googlegroups.com
On Mon, Jan 14, 2013 at 5:31 PM, Simon Ochsenreither <simon.och...@gmail.com> wrote:
You already prohibit 2 of 3 reflection APIs which is a good thing, but you should probably also consider adding javax.lang.model, as they plan to add a runtime implementation in the future (by the way, does this sound familiar :-D) and who knows how they manage to mess it up this time.

I should mention that checking this list might also slow down the Inliner a touch.

-jason

Paul Phillips

unread,
Jan 14, 2013, 11:39:02 AM1/14/13
to scala-i...@googlegroups.com

On Mon, Jan 14, 2013 at 8:03 AM, Jason Zaugg <jza...@gmail.com> wrote:
Anyway, this was a bigger can of worms than I thought, and I'm not sure what to do with this.

It's a giant can. It is not amenable to one-size-fits-all solutions, no way.

We should have a user-pluggable interface to the optimizer allowing for custom logic as to what methods are eligible for inlining. The default implementation would have a very short blacklist and we call it a day. That spreads out the worms on the people for whom the specifics make any difference, leaving our can free for other worms.

Simon Ochsenreither

unread,
Jan 14, 2013, 11:51:38 AM1/14/13
to scala-i...@googlegroups.com
Have a look at:

+ /**
+ * Is this method a caller-sensitive method?
+ * I.e., does it call Reflection.getCallerClass or a similer method
+ * to ask about the identity of its caller?
+ */

in http://hg.openjdk.java.net/jdk8/tl/jdk/rev/762eee5e6e16

Looks like Java will be getting a @sun.reflect.CallerSensitive annotation sooner or later, which we can just check.

Paul Phillips

unread,
Jan 14, 2013, 12:07:26 PM1/14/13
to scala-i...@googlegroups.com
On Mon, Jan 14, 2013 at 8:51 AM, Simon Ochsenreither <simon.och...@gmail.com> wrote:
Looks like Java will be getting a @sun.reflect.CallerSensitive annotation sooner or later, which we can just check.

That's very useful information, thanks a lot.

Paul Phillips

unread,
Jan 14, 2013, 12:11:48 PM1/14/13
to scala-i...@googlegroups.com
On Mon, Jan 14, 2013 at 8:51 AM, Simon Ochsenreither <simon.och...@gmail.com> wrote:
Looks like Java will be getting a @sun.reflect.CallerSensitive annotation sooner or later, which we can just check.

Also, this reinforces the wisdom of pursuing the minimal solution. I like the idea of making it possible to influence key optimizer decisions from user level regardless of whether we need it for this, and taking that approach would make it trivial to change the default implementation to check for that annotation whenever it became available. But we don't even need to do that much at the moment. I think Class.forName is the dominating concern, all else is either sufficiently unlikely to arise in practice or sufficiently intractable to handle correctly that we can reasonably punt.

Matthew Pocock

unread,
Jan 14, 2013, 12:28:59 PM1/14/13
to scala-i...@googlegroups.com
For now, would putting a black-list in a well-known plain text file that scalac can find as a resource work? As long as it uses getResources, we can put any number of them in the compiler's classpath. Add a -inlineBlacklistFile option for belt-and-braces?

Matthew
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle University
skype: matthew.pocock
tel: (0191) 2566550

Simon Ochsenreither

unread,
Jan 14, 2013, 12:32:58 PM1/14/13
to scala-i...@googlegroups.com

Also, this reinforces the wisdom of pursuing the minimal solution.

I agree, let's just call MethodHandleNative.isCallerSensitive and let the JDK do our job.

Ismael Juma

unread,
Jan 14, 2013, 2:39:03 PM1/14/13
to scala-i...@googlegroups.com
On Mon, Jan 14, 2013 at 4:51 PM, Simon Ochsenreither <simon.och...@gmail.com> wrote:
Have a look at:

+ /**
+ * Is this method a caller-sensitive method?
+ * I.e., does it call Reflection.getCallerClass or a similer method
+ * to ask about the identity of its caller?
+ */

in http://hg.openjdk.java.net/jdk8/tl/jdk/rev/762eee5e6e16

Paolo G. Giarrusso

unread,
Jan 14, 2013, 9:15:30 PM1/14/13
to scala-i...@googlegroups.com
Your message prompts a much more basic question (which could allow a much simpler fix, namely blacklisting the whole Java class library): how can we ever inline JDK's code while keeping it compatible with changes in the standard Java library? We inline Java method X from JDK library Y, that method's fixed in next release of the JDK, but since the application is not recompiled the fix is not included.

This can have security implication; If we assume that the fix is for a security bug, a Scala application is potentially affected if any Scala code it uses (libraries or the application itself) was compiled with -optimise on a vulnerable machine.
Please tell me I'm missing something here. Please.

Such problems potentially generalize to any cross-library inlining, but only if the library contained the inlined code is allowed to be upgraded - is that on by default in when you create a POM file? I have no clue on publishing libraries.
Also, this gets fun when you inline code from a buggy cryptography library, for instance, or (for different reasons) when you inline enough code to depend on changing implementation details of a library (not sure if that's possible in Scala though).

Jason Zaugg

unread,
Jan 15, 2013, 3:16:04 AM1/15/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 3:15 AM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:
Your message prompts a much more basic question (which could allow a much simpler fix, namely blacklisting the whole Java class library): how can we ever inline JDK's code while keeping it compatible with changes in the standard Java library? We inline Java method X from JDK library Y, that method's fixed in next release of the JDK, but since the application is not recompiled the fix is not included.

This can have security implication; If we assume that the fix is for a security bug, a Scala application is potentially affected if any Scala code it uses (libraries or the application itself) was compiled with -optimise on a vulnerable machine.
Please tell me I'm missing something here. Please.

Such problems potentially generalize to any cross-library inlining, but only if the library contained the inlined code is allowed to be upgraded - is that on by default in when you create a POM file? I have no clue on publishing libraries.
Also, this gets fun when you inline code from a buggy cryptography library, for instance, or (for different reasons) when you inline enough code to depend on changing implementation details of a library (not sure if that's possible in Scala though).

Thanks for raising this.

Another variation thereof: inline a method body from the compile time JDK, which refers to classes/methods that are not available on some alternative runtime JDK.

A reasonable heuristic to approximate disabling 'cross library inlining' might be to only allow inlining from code that is provided to the compiler as source files or as .class files, but not as JAR files. Inlining of methods in the Scala standard library has all the same implications as the Java standard library, however if you disable that you lose an important class of performance wins.

We have to think very carefully about defaults here, and find a way balance the needs of the 'closed world' users who want maximum performance vs the 'open world' users who need safety in the face of unknown runtime environments.

-jason

Jason Zaugg

unread,
Jan 15, 2013, 3:29:34 AM1/15/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 9:16 AM, Jason Zaugg <jza...@gmail.com> wrote:
We have to think very carefully about defaults here, and find a way balance the needs of the 'closed world' users who want maximum performance vs the 'open world' users who need safety in the face of unknown runtime environments.

And, dream of the day when we can offload more of the job to HotSpot, which is in a better position for simultaneous cake possession/consumption.

BTW, I didn't find any literature about the security impact of code inlining. Maybe it is deemed too obvious to warrant much discussion? Or my keywords weren't up to scratch today.

-jason

Paolo G. Giarrusso

unread,
Jan 15, 2013, 10:17:47 AM1/15/13
to scala-i...@googlegroups.com
> Inlining of methods in the Scala standard library has all the same implications as the Java standard library,
But the problem didn't exist before 2.10 - moving from 2.9.1 to 2.9.2 required recompilation anyway, so inlining was safe.
> however if you disable that you lose an important class of performance wins.
Agreed, so inlining won't be disabled.

Therefore, if there's a security bug in the Scala library, we're in trouble.

But was there ever a security bug in the Scala library? Google "scala library vulnerability" points to no relevant result, and that library doesn't include say SSL code, so maybe we're good. Lesson: do *not* include a cryptography library within the standard library. Alternatively, prevent inlining from this library. We discussed making the inliner more configurable, I'd propose this as a use case to support.

While I just argued that we're reasonably safe, the history of security bugs tells me that my reasoning doesn't hold water. 

Moreover, the standard library does not include code messing with classloaders and security privileges, does it? Thinking of reflection, I'm not so sure anymore. Eugene, what happens if some code C is running with low privileges and uses reflection (which is on the boot classpath, hence a trusted library) to load new code - will the new code D be loaded by a different classloader than C? I'd guess yes.
Can D's classloader be more privileged than C? If it can't, is it by accidental lack of bugs, or is such a privilege escalation bug impossible?
The best I could do was Google "distributing security-related patches to statically linked libraries" (no quotes) - below I discuss how I got there.

At first, I didn't find anything either, but I wonder how many other systems have cross-module inlining without dependency checking. Most cross-module inlining is done by VMs, which don't have that problem and are in the perfect position for inlining; the JVM's only problem is that it's been tuned for decades to a non-functional language, so it has the wrong inlining heuristics.
When I wrote my first comment in this thread, I was thinking of GHC ("Secrets of the Glasgow Haskell Compiler inliner"): it does cross-module inlining, but has static linking and dependency checking at compilation time.

C can have that problem, except that historically the only analogue of cross-module inlining was static linking, which is similar only for our current discussion.
Googling "distributing security-related patches to statically linked libraries" (no quotes) finds relevant discussions, but most is not so interesting. This page is telling though:

http://fedoraproject.org/wiki/Packaging:Guidelines#Statically_Linking_Executables
"If you link statically against a library, add yourself to the initialcc list for the library so you can watch for any security issues or bug fixes for which you'd want to rebuild your package against a new version of the library."

It seems we need to educate Scala users to do the same - even regardless of -optimize. If library A is patched, you need to update it in any case, plus any Scala libraries which use it and were built with -optimize (transitive dependencies where all edges "used" -optimize also count).

Alex Cruise

unread,
Jan 15, 2013, 1:14:54 PM1/15/13
to scala-i...@googlegroups.com
Is @noinline (http://www.scala-lang.org/api/current/index.html#scala.noinline) germane to this discussion?  Does it still do what it says on the tin?  Should it be more widely publicized? :)

-0xe1a

Jason Zaugg

unread,
Jan 15, 2013, 1:54:58 PM1/15/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 7:14 PM, Alex Cruise <al...@cluonflux.com> wrote:
Is @noinline (http://www.scala-lang.org/api/current/index.html#scala.noinline) germane to this discussion?  Does it still do what it says on the tin?  Should it be more widely publicized? :)

Perhaps what isn't widely publicized it at the inliner can inline code from a third party JAR (e.g. the Java standard library). We need some configurable means (with sane defaults) to allow you to selectively mark third party code as @noinline.

-jason

Grzegorz Kossakowski

unread,
Jan 15, 2013, 2:30:50 PM1/15/13
to scala-i...@googlegroups.com
I think I'd prefer to get rid of heuristics all together and just have guaranteed inlining of @inline defs. Advantages are:
  • predictability; you mark defs as @inline only if you are reasonably sure that it's safe (code is stable, no security issues, etc.)
  • much faster inliner because it doesn't need to speculate
  • robustness against refactorings; these days you can have performance regression caused by little refactoring of your code because heuristics do not kick in
The point I'm trying to make is that JVM has its own set of heuristics and we should rely on them where it makes sense and only use our own tools to aid JVM when it's known that JIT has hard time to optimize (e.g. higher order methods that are mega-morphic).

Combining two set of heuristics JVM's and Scala's does not sound like recipe for success in my opinion.

--
Grzegorz Kossakowski
Scalac hacker at Typesafe
twitter: @gkossakowski

√iktor Ҡlang

unread,
Jan 15, 2013, 2:35:29 PM1/15/13
to scala-i...@googlegroups.com
+1
--
Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

Erik Osheim

unread,
Jan 15, 2013, 2:43:00 PM1/15/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 11:30:50AM -0800, Grzegorz Kossakowski wrote:
> I think I'd prefer to get rid of heuristics all together and just have
> guaranteed inlining of @inline defs. Advantages are:
>
> - predictability; you mark defs as @inline only if you are reasonably
> sure that it's safe (code is stable, no security issues, etc.)
> - much faster inliner because it doesn't need to speculate
> - robustness against refactorings; these days you can have performance
> regression caused by little refactoring of your code because heuristics do
> not kick in

Agreed.

If a developer incorrectly marks a method as @inline that is their bug.

-- Erik

Paolo Giarrusso

unread,
Jan 15, 2013, 2:50:48 PM1/15/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 8:30 PM, Grzegorz Kossakowski
<grzegorz.k...@gmail.com> wrote:
That's a very good idea for the standard library, and as an option for
many other libraries. Heck, it's even a good *default policy*, since
it gives security by default.

But maintaining @inline annotations can be quite expensive: *if* the
current or the experimental optimizer can achieve, by default, better
performance because of some good heuristics (say, inlining
higher-order functions together with their concrete arguments - as
done always (?) by Delite), it would be bad to throw that away;
especially, some tool should support developers to find where to add
@inline; currently you need to do profiling, understand Hotspot inline
caching/inlining and inspect inlining decision from the JVM. I'm not
yet really able to do all that, even though I tried (up to some
point).

Overall, it seems time to invoke the "mechanism not policy" Unix
tenet, which leads to Paul's idea. If I'm releasing an application,
there's no extra security risk in inlining most libraries, since the
user won't change their version anyway - especially if I choose that
consciously.

Best,
Paolo

Alex Cruise

unread,
Jan 15, 2013, 3:52:10 PM1/15/13
to scala-i...@googlegroups.com
Uh, wow!  This strikes me as 0xABad1dea in the general case.  Everyone likes binary compatibility and separate compilation--we might be unable to provide it as much as we'd like, but other people can and do, and inlining into *their* bytecode seems like a recipe for... surprises. :)

This is admittedly naïve, but I would want the inliner to:
- Be aggressive with code that's being compiled during *this* run, driven by heuristics and/or annotations
- Be moderate when inlining into bytecode that was compiled with the exact-same-version Scala compiler
- Be a little more cautious when loading bytecode that was compiled with a binary-compatible Scala compiler
- Otherwise, for arbitrary bytecode, including that compiled by older-than-binary-compatible versions of Scala, be extremely cautious--to the point of doing no inlining at all, maybe unless guided by a whitelist.

I haven't added an -optimize dimension to this list, but surely It Shouldn't Be Too Hard to cook up a set of rules to include that.

-0xe1a

Simon Ochsenreither

unread,
Jan 15, 2013, 7:08:41 PM1/15/13
to scala-i...@googlegroups.com
@sun.reflect.CallerSensitive?

Johannes Rudolph

unread,
Jan 16, 2013, 4:07:14 AM1/16/13
to scala-i...@googlegroups.com
On Tue, Jan 15, 2013 at 8:30 PM, Grzegorz Kossakowski
<grzegorz.k...@gmail.com> wrote:
> The point I'm trying to make is that JVM has its own set of heuristics and
> we should rely on them where it makes sense and only use our own tools to
> aid JVM when it's known that JIT has hard time to optimize (e.g. higher
> order methods that are mega-morphic).
>
> Combining two set of heuristics JVM's and Scala's does not sound like recipe
> for success in my opinion.

If the two sets of heuristics differ too much, then yes. But to inline
successfully the inliner must have _some_ idea about if an inlining is
effective or not. And it usually has to take the call-site into
account as well. Do you want to replace the calculated heuristic of
the compiler with a simple static heuristic of
"the-programmer-has-said-so" which may have too little contextual
information to know the call-sites up front and other details of the
JVM that may matter.

IMO the deficiency of scalac's optimizer has always been the fact that
it uses a heuristic _before_ it takes the decision and doesn't
evaluate the result of its action afterwards to throw away detrimental
"optimizations".

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

Stefan Zeiger

unread,
Jan 16, 2013, 5:51:59 AM1/16/13
to scala-i...@googlegroups.com
Is there any situation where you'd want third-party code to be inlined? This will make a total mess of binary compatibility if you end up with parts from different JARs in your code.

-sz

Paolo Giarrusso

unread,
Jan 16, 2013, 10:03:13 AM1/16/13
to scala-i...@googlegroups.com
You mean different versions of the same library, right? We've discussed this, but nobody said yet if e.g. Maven or SBT allow that.
 
In this thread we already discussed why you want to inline some third-party code, but I'll summarize a few cases:
* You do want to inline at least some code from the Scala standard library.
* In an application you want to do global inlining (where appropriate for performance).
* More in general, in a library you can inline code from another library *iff* that other library is already constrained to a fixed version (which I guess is the case in an SBT project). An application is an instance of this case (since you ship the application together with all its dependencies).

--
Paolo

Matthew Pocock

unread,
Jan 16, 2013, 10:31:07 AM1/16/13
to scala-i...@googlegroups.com
On 16 January 2013 15:03, Paolo Giarrusso <p.gia...@gmail.com> wrote:
You mean different versions of the same library, right? We've discussed this, but nobody said yet if e.g. Maven or SBT allow that.

Maven potentially allows this by using artifact version ranges. I think osgi has a similar mechanism. My experience is that these are used very sparingly in the wild, but that may just be my personal experience.

In this thread we already discussed why you want to inline some third-party code, but I'll summarize a few cases:
* You do want to inline at least some code from the Scala standard library.
* In an application you want to do global inlining (where appropriate for performance).
* More in general, in a library you can inline code from another library *iff* that other library is already constrained to a fixed version (which I guess is the case in an SBT project). An application is an instance of this case (since you ship the application together with all its dependencies).

If you inline across jar boundaries, you're making a commitment to bind to that exact bytecode. This is a much stronger commitment than binding to an API (with or without implied consistent behaviour), which is the contract that is usually modelled using major/minor version numbers.

There is the transitive case - library A inlines code from library B, and your project inlines code from A that resulted from this inlining. Your project depends directly upon A. B is modified and version bumped. A is then built against the new version of B, so now A's version must be bumped purely because of the change in dependencies, otherwise your inlining in your app from A is stale.

Say your project relies on the standard lib and has inlined a bug in a collection implementation (not that such things happen...). In the olden days, you could rescue this by running your code against a standard lib with the bug fixed. In the brave new world of inlining, this is not sufficient. You need to recompile.

There are loads of other snakes in this pit, but I think the take-home is that if you support inlining across module boundaries (between jars) then you need to be fastidious about versioning these jars and making them as orthogonal and self-contained as possible, with clear transitive dependencies and bullet-proof plans for bumping version numbers. To my mind, this is another strong argument in favour of small, modular jars - more jars means less bytecode is attached to any given version number. So, if you make a change, more of the inlining remains provably valid.

The alternative is to annotate classes/methods with their inlined dependencies and bytecode checksums, and have some link-time hook in the JVM that validates the checksums for these dependencies. I have no idea how to implement this, and it sounds like a nightmare. I wouldn't wish it on a PhD student.

I would be interested to see how aggressive inlining affects how much work ProGuard can do - I'd hope that explicit references to many library classes would evaporate along the way, but perhaps this is unrealistic. It may be worth benchmarking at some point though.

Matthew


--
Paolo

Paolo Giarrusso

unread,
Jan 16, 2013, 11:16:03 AM1/16/13
to scala-i...@googlegroups.com
On Wed, Jan 16, 2013 at 4:31 PM, Matthew Pocock <turingate...@gmail.com> wrote:
On 16 January 2013 15:03, Paolo Giarrusso <p.gia...@gmail.com> wrote:
You mean different versions of the same library, right? We've discussed this, but nobody said yet if e.g. Maven or SBT allow that.

Maven potentially allows this by using artifact version ranges. I think osgi has a similar mechanism. My experience is that these are used very sparingly in the wild, but that may just be my personal experience.

Thanks for your answer. I'd also expect these to be used sparingly, since they make sense only when using libraries with stable ABIs, which are the exception given how hard it is.

In this thread we already discussed why you want to inline some third-party code, but I'll summarize a few cases:
* You do want to inline at least some code from the Scala standard library.
* In an application you want to do global inlining (where appropriate for performance).
* More in general, in a library you can inline code from another library *iff* that other library is already constrained to a fixed version (which I guess is the case in an SBT project). An application is an instance of this case (since you ship the application together with all its dependencies).

If you inline across jar boundaries, you're making a commitment to bind to that exact bytecode. This is a much stronger commitment than binding to an API (with or without implied consistent behaviour), which is the contract that is usually modelled using major/minor version numbers.
Note that when you bind to an exact version of a library, you're making that commitment anyway. You still have a point, but that's not for the common case.

Once again, I don't argue that cross-module inlining should be the default, except when the developer indicates it wants it:
* you're inlining a method marked @inline. The author better make that stable or be careful with his policy. Grzegorz Kossakowski argued this should be the only case.
* I'd argue that the developer should be able to tell the compiler additional policies. Of course, he needs to know what he's doing.

As I argued before, this has security implication on how hard it is to ship a security patch.

[...] To my mind, this is another strong argument in favour of small, modular jars - more jars means less bytecode is attached to any given version number. So, if you make a change, more of the inlining remains provably valid.

Good point.

The alternative is to annotate classes/methods with their inlined dependencies and bytecode checksums, and have some link-time hook in the JVM that validates the checksums for these dependencies. I have no idea how to implement this, and it sounds like a nightmare. I wouldn't wish it on a PhD student.

I'm not arguing for this, but I think that's close to what the Glasgow Haskell Compiler (GHC) does during compilation to check whether something needs to be recompiled.

I would be interested to see how aggressive inlining affects how much work ProGuard can do - I'd hope that explicit references to many library classes would evaporate along the way, but perhaps this is unrealistic.
The JVM does this, but it requires escape analysis, which at some point will need to list all implementations of a given method. But you don't have that at compile-time, because in Java you can load new code at runtime. The JVM has the luxury of invalidating optimizations if needed, when code is loaded, compile-time tools don't.

Remember that we need inlining only for things where Java has the wrong heuristics (e.g. higher-order methods), but it's otherwise a hack, so we should be careful with doing too much.
-- 
Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

Miguel Garcia

unread,
Jan 18, 2013, 10:18:12 AM1/18/13
to scala-i...@googlegroups.com

A summary on how the experimental optimizer goes about inlining can be found at http://magarciaepfl.github.com/scala/

It doesn't inline JDK methods, among other advantages. Thread: https://groups.google.com/d/topic/scala-internals/ptK35Lp01IA/discussion


Miguel
http://lampwww.epfl.ch/~magarcia/

Matthew Pocock

unread,
Jan 18, 2013, 10:30:33 AM1/18/13
to scala-i...@googlegroups.com
I use this pattern for interoperability with Java sometimes:

class Foo(private var name: String) {
  def getName = name
  def setName(name: String) { this.name = name }
}

Will the experimental optimizer inline the private accessors for `name` into the get/sets? As they are only used there and not referred to anywhere else and can not be, will the scala var accessor pair be optimized away?

Thanks,

Matthew

Paolo Giarrusso

unread,
Jan 18, 2013, 10:39:43 AM1/18/13
to scala-i...@googlegroups.com
On Fri, Jan 18, 2013 at 4:18 PM, Miguel Garcia <miguel...@tuhh.de> wrote:
A summary on how the experimental optimizer goes about inlining can be found at http://magarciaepfl.github.com/scala/

I'm confused about the first warning example you give. It seems clear why *calling List.loop$1* is prevented by access control, and it seems that's the complaint - but can't that be fixed by also inlining loop$1 in the caller? Now, either loop$1 uses private members (but it doesn't seem to be the case, looking at the actual List) or @inline must be added to def loop (I would have expected that to be defaulted). If you could also answer on the webpage itself for future reference, that'd be perfect.

SpecializeTypes.scala:1166: warning: Closure-inlining failed because
  scala/collection/immutable/List::mapConserve(Lscala/Function1;)Lscala/collection/immutable/List;
contains instruction 
  INVOKESPECIAL scala/collection/immutable/List.loop$1 (Lscala/collection/mutable/ListBuffer;Lscala/collection/immutable/List;Lscala/collection/immutable/List;Lscala/Function1;)Lscala/collection/immutable/List;
that would cause IllegalAccessError from class scala/tools/nsc/transform/SpecializeTypes
        val parents1 = parents mapConserve specializedType

My other question would be: since @inline must be explicit, existing code bases might well need more @inline annotations. How hard is to add them?

Miguel Garcia

unread,
Jan 18, 2013, 10:43:22 AM1/18/13
to scala-i...@googlegroups.com

In the example, after adding @inline to getters and setters:

class Foo(private var name: String) {
  @inline def getName = name
  @inline def setName(name: String) { this.name = name }
}

The experimental optimizer will inline accesses to them. For a getter what gets inlined is its body, ie:

public java.lang.String getName();
  Code:
   Stack=1, Locals=1, Args_size=1
   0:    aload_0
   1:    invokevirtual    #17; //Method Foo$$name:()Ljava/lang/String;
   4:    areturn


Another level of indirection! The getter-behind-the-scenes in turn looks like:

public java.lang.String Foo$$name();
  Code:
   Stack=1, Locals=1, Args_size=1
   0:    aload_0
   1:    getfield    #12; //Field Foo$$name:Ljava/lang/String;
   4:    areturn

In fact, the inliner has done its job: cutting down indirection by one level. Now you might say, I want the remaining indirection level also removed. Fine, that's another optimization. It would be great to come up with a general recipe for that and similar cases.


Miguel
http://lampwww.epfl.ch/~magarcia/

Miguel Garcia

unread,
Jan 18, 2013, 10:46:03 AM1/18/13
to scala-i...@googlegroups.com

> @inline must be added to def loop (I would have expected that to be defaulted)

The experimental optimizer doesn't add any @inline annotations on its own. In the example, looks like that would fix the problem.


Miguel
http://lampwww.epfl.ch/~magarcia/

Matthew Pocock

unread,
Jan 18, 2013, 6:35:11 PM1/18/13
to scala-i...@googlegroups.com

OK. Is it possible for the private var accessors to be marked @inline? I know the JVM will be doing this for me but it is the reduction in bytecode that I really care about here.

Sent from my android - may contain predictive text entertainment.

Miguel Garcia

unread,
Jan 18, 2013, 6:47:37 PM1/18/13
to scala-i...@googlegroups.com

I'll add it to the list of candidate optimizations to be implemented (aka ToDo list). I agree code size reductions are important.

Talking about candidate optimizations, an appeal to all bytecode connoisseurs on scala-internals: Community development is *feasible* for the new optimizer:
  (a) it is documented,
  (b) it consists of several small transforms each of them easy to understand on its own, and
  (c) it performs bytecode manipulation via the Tree API of ASM, itself documented in Ch. 6 to 9 of http://download.forge.objectweb.org/asm/asm4-guide.pdf

See you at http://magarciaepfl.github.com/scala/


Miguel
http://lampwww.epfl.ch/~magarcia/

Paul Phillips

unread,
Jan 18, 2013, 6:52:16 PM1/18/13
to scala-i...@googlegroups.com
On Fri, Jan 18, 2013 at 3:35 PM, Matthew Pocock <turingate...@gmail.com> wrote:

OK. Is it possible for the private var accessors to be marked @inline?

You might try this, which I saw in a recent contribution. I don't know if it does the job, or in what cases.

  /*
   * Forcing direct fields access using the @inline annotation helps speed up
   * various operations (especially smallest/greatest and update/delete).
   *
   * Unfortunately the direct field access is not guaranteed to work (but
   * works on the current implementation of the Scala compiler).
   *
   * An alternative is to implement the these classes using plain old Java code...
   */
  sealed abstract class Tree[A, +B](
    @(inline @getter) final val key: A,
    @(inline @getter) final val value: B,
    @(inline @getter) final val left: Tree[A, B],
    @(inline @getter) final val right: Tree[A, B])
  extends Serializable {
    @(inline @getter) final val count: Int = 1 + RedBlackTree.count(left) + RedBlackTree.count(right)
    def black: Tree[A, B]
    def red: Tree[A, B]
  }

Reply all
Reply to author
Forward
0 new messages