while I had a somewhat workable solution to create some simple Android
apps with Scala, I've now come to the point (as well) where Dalvik
fails either while dexopt'ing a proguarded Scala program or later at
runtime when it tries to load a class (basically reported in [1]). I'm
starting this thread to gather some more information to find out how
this problem can be solved by Scala, Android, or at all.
The basic problem lies in in dalvik's custom memory allocator,
LinearAlloc. Without going into details, it seems like that allocator
is used similar to the PermGen in HotSpot to allocate class data, like
vtables etc. The problem here is that this allocation region is
statically fixed to 5 MB [2] per classloader.
For a program that fails consider the single line from SI-4620:
class ObservableTest extends ArrayBuffer[Int]
Even if proguarded, ArrayBuffer alone has such a trail of dependencies
that those 5MB are not enough.
I patched dexopt to log for what purpose and what class it is
allocating memory, here's the output [3].
(The line 'D/dalvikvm(14166): CLASS: linking 'Ljava/lang/Class;'...'
always comes in between the corresponding entries for the class)
As you can see at the end there are classes which need big amounts of
memory, I think that's because the huge number of methods in those
classes coming from several interfaces.
As a starter, here are some suggestions how to go further from here:
* Find out which classes exactly cause the problem, and how big the
memory would have to be to support Scala
* Try to use multiple class loaders to have multiple allocation regions of 5 MB
* Work with the Android team to find a better general allocator scheme
* Try to reduce the footprint (of the most common parts) of the Scala library
* Find out why proguard can't shrink Scala's library further into
better consumable bits
* Create a more lightweight Scala library for Android development
More to come...
--
Johannes
[1] https://issues.scala-lang.org/browse/SI-4620
[2] LinearAlloc.c : #define DEFAULT_MAX_LENGTH (5*1024*1024)
[3] https://gist.github.com/1214972
-----------------------------------------------
Johannes Rudolph
http://virtual-void.net
Bye,
Simon
I certainly hope that at some point these restrictions will be lifted in Android (I know that the Clojure community is butting up against the same limitations at the moment). But having said that:
On 13 Sep 2011, at 21:39, Johannes Rudolph wrote:
> * Try to reduce the footprint (of the most common parts) of the Scala library
> * Find out why proguard can't shrink Scala's library further into
> better consumable bits
> * Create a more lightweight Scala library for Android development
One or more of these options, it strikes me, definitely has to be part of the solution. Resource constrained devices are going to be with us for some time, and if Scala can't sensibly address them, that's going to be a very significant chink in its armour.
We currently use Scala very heavily on Android, but at the moment only for test code, not production. I was hoping that we were getting close to the point where that could change, but unfortunately the opposite seems to be true :-(
Anyway, thanks again for your efforts!
--
paul.butcher->msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: pa...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
-
Stefan
2011/9/14 Paul Butcher <pa...@paulbutcher.com>:
This could probably be fixed--albeit with a performance penalty--fairly quickly by compiling the library with specialization turned off.
On Wed, Oct 19, 2011 at 6:46 PM, Rex Kerr <ich...@gmail.com> wrote:This could probably be fixed--albeit with a performance penalty--fairly quickly by compiling the library with specialization turned off.
I'd be interested in an experiment to see if it was true. If yes, we might want to ship with an alternate "slim" library for Android.
What makes you think so? Looking at the dump from my original post, my
greatest hopes right now are that (if there's a "quick fix") the
proposed changes to the view hierarchy could improve things quite a
lot.
--
Johannes
The critical metric isn't size, it's call sites. No more than 64k
(method definitions) + (calls to methods) is allowed.
Smaller is better, obviously, but I don't think size is the blocking
problem right now.
--
James Moore
ja...@restphone.com
http://jamesmoorecode.blogspot.com/
--
On Tue, Sep 13, 2011 at 10:39 PM, Johannes Rudolph
<johannes...@googlemail.com> wrote:
> * Find out which classes exactly cause the problem, and how big the
> memory would have to be to support Scala
To find out how much memory would be needed I compiled a dalvik
version with increased LinearAlloc size. The example from the ticket
[1] would need a LinearAlloc size of about 10 MB (twice the current
size).
Then I checked what exactly needs those MBs of memory and I think I've
pretty much identified the current problem with the DalvikVM. See this
snippet (https://gist.github.com/1426684), which collects all of the
interfaces a class implements in a naive way:
scala> import collection.JavaConversions._
import collection.JavaConversions._
scala> def allIf(clazz: Class[_]): Seq[String] =
clazz.getInterfaces.map(_.toString) ++
clazz.getInterfaces.flatMap(allIf)
allIf: (clazz: Class[_])Seq[String]
scala> val theClazz =
Class.forName("scala.collection.immutable.StreamViewLike$$anon$10")
theClazz: Class[_] = class scala.collection.immutable.StreamViewLike$$anon$10
scala> val res0 = { allIf(theClazz) }
res0: Seq[String] = ...
scala> res0.size
res16: Int = 9223
scala> res0.distinct.size
res17: Int = 49
9223 ?!? What you see is multiple interface inheritance at work.
Unfortunately, the `allIf` function roughly corresponds to the way the
dalvik vm currently collects the full set of interfaces a
class/interface implements. The problem is that the DalvikVM doesn't
remove the duplicate interfaces in a final step (there was code to do
that, but is currently commented for some problems with other
functionality). Each interface needs at least 8 bytes of memory and
this is only one of the problematic classes. I guess this was never
better optimized because an interface hierarchy as complicated as this
is unusual in Java. I attached the hierarchy of the given class
(without ScalaObject) for illustration.
The question is if there is anything on the Scala side which would
improve the situation. The change of providing abstract classes for
some of the classes in the hierarchy didn't do much good here
unfortunately (because overall the hierarchy itself didn't change
much).
But there is something simple which could be done: There are a lot of
useless interface declarations which are already covered by super
interfaces. Most obvious example is ScalaObject which is a super
interface of all those interfaces. Removing all those interfaces would
mean a reduction to approx. 2000 interfaces for this example (but less
for other less spectacular cases).
> * Try to use multiple class loaders to have multiple allocation regions of 5 MB
That won't work, there is some code which looks as if each ClassLoader
would be getting its own region of 5MB but in reality this is not
(yet?) implemented in dalvik.
> * Find out why proguard can't shrink Scala's library further into better consumable bits
If you think about how shrinking works, you can quite easily see that
finding the minimal set of classes/methods needed for execution is
undecidable in theory (if you can't say for sure that a program halts,
neither you can say - for some points in the program - that those
points will be reached, so you can't prune from there on). In practice
you would have to optimistically include this code but this may be not
the biggest problem (because common programs may be sufficiently
simple). What is really hard, is handling virtual calls. As long as
you can't be sure what exactly the receiver of a virtual call is you
would have to include all possible subclasses. Now think about what
this means if you use Scala's Function classes. I think his explains
why proguard has problems with the highly inter-dependent collection
classes. There's academic literature on this topic, so maybe there is
a good enough solution which just no one has implemented for Java
bytecode.
--
Johannes
[1] https://github.com/humcycles/dexfailure
On Mon, Dec 5, 2011 at 3:44 PM, Glenview Jeff <glenvi...@gmail.com> wrote:
> There was an Android bug filed in March 2010. The present status is
> "working as intended." Star it and add your feedback.
--
Johannes
I don't know a bug number, but they're aware of the issue. When I
talked to some Dalvik guys at Google IO this year, they knew it was an
issue for scala, and thought that scala was an indicator that other
people would be hitting it too ("canary in the coal mine" was the
phrase used). They wanted to change it, but didn't have any
dates/releases for when that might happen.
The interface minimization is checked in; the above now produces
scala> res0.size
res2: Int = 2351
scala> res0.distinct.size
res3: Int = 49
(interface scala.ScalaObject,634)
(interface scala.collection.GenTraversableOnce,263)
(interface scala.collection.Parallelizable,233)
(interface scala.collection.GenTraversableLike,233)
(interface scala.collection.generic.HasNewBuilder,156)
(interface scala.collection.generic.GenericTraversableTemplate,126)
(interface scala.collection.GenTraversable,126)
(interface scala.collection.GenIterableLike,77)
(interface scala.collection.GenTraversableViewLike,58)
(interface scala.collection.GenIterable,50)
(interface scala.collection.GenTraversableView,49)
(interface scala.collection.TraversableLike,30)
(interface scala.collection.generic.FilterMonadic,30)
(interface scala.collection.TraversableOnce,30)
(interface scala.collection.GenIterableViewLike,29)
(interface scala.Equals,27)
(interface scala.collection.GenIterableView,23)
(interface scala.collection.Traversable,18)
(interface scala.collection.GenSeqLike,15)
(interface scala.collection.GenSeq,12)
(interface scala.collection.IterableLike,12)
(interface scala.collection.GenTraversableViewLike$Transformed,11)
(interface scala.collection.Iterable,9)
(interface scala.collection.GenSeqViewLike,9)
(interface scala.collection.TraversableViewLike,9)
(interface scala.collection.TraversableView,9)
(interface scala.collection.ViewMkString,9)
(interface scala.collection.GenIterableViewLike$Transformed,8)
(interface scala.collection.IterableViewLike,6)
(interface scala.collection.GenSeqView,6)
(interface scala.collection.IterableView,6)
(interface scala.collection.GenSeqViewLike$Transformed,3)
(interface scala.Function1,3)
(interface scala.collection.SeqView,3)
(interface scala.collection.Seq,3)
(interface scala.collection.IterableViewLike$Transformed,3)
(interface scala.collection.SeqLike,3)
(interface scala.collection.TraversableViewLike$Transformed,3)
(interface scala.collection.SeqViewLike,3)
(interface scala.PartialFunction,3)
(interface scala.collection.SeqViewLike$Transformed,2)
(interface scala.collection.GenIterableViewLike$ZippedAll,2)
(interface scala.collection.immutable.StreamViewLike,1)
(interface scala.collection.immutable.StreamViewLike$ZippedAll,1)
(interface scala.collection.SeqViewLike$ZippedAll,1)
(interface scala.collection.GenSeqViewLike$ZippedAll,1)
(interface scala.collection.IterableViewLike$ZippedAll,1)
(interface scala.collection.immutable.StreamView,1)
(interface scala.collection.immutable.StreamViewLike$Transformed,1)
I'm marking this as "working as intended," but that's really not the whole story:
It turns out that you have made the first report we've seen of anyone running into Dalvik's existing limit of
65536 method references per dex file.
In the short term, we are going to fix the error message to be less opaque. In the long term, we will do a rev of
the format to allow for "jumbo" method references (and field references, while we're at it). We knew we were
seeing string counts approaching the 16-bit limit before we shipped 1.0, and so we introduced the const-
string/jumbo variant of the const-string opcode. However, we didn't think we'd see method counts hit the
limit for quite a while. You have made us rethink our timeline!
As you noticed, by splitting your output into multiple dex files, you are neatly working around the problem.
You will of course have a bit more to do to make multiple dex files work as part of an Android application, but
all the right Android/Dalvik library support should be there for you to do that.
Thanks for the report, and I'm sorry that I can't promise a quick solution to the problem, as an executable
format rev is no small matter.
Oh, I didn't want to dispute that this may be still an issue, it's
just not the current blocker. At least not the one I'm seeing here. Is
anyone else still blocked by the bug from the issue?
danfuzz (presumably at Google)
Dan is the creator and main architect of Dalvik.
I don't know: I left Google and stopped working on Android a couple months ago...You've always been able to load additional dex files into an app. I don't deny that it's extra effort in the build system and to put together the app bootstrap code, but it only has to be set up once for the entire Scala community.
http://code.google.com/p/android/issues/detail?id=22586
Actually, the Android code once contained a fix for this issue which
was commented out later on. However, I think the reason why the old
fix had to be inactivated is invalid and then I went on and fixed the
issue blocking this one as well, so we might have good luck and have
this problem fixed in dalvik before 2015.
--
Johannes
https://gist.github.com/1434551#file_src%2Ftest.java
--
Johannes
If scala-test compiller suite pass without any errors than scala ready for tablet devices. Maybe to write android activity, that allow to run scala-test suite in adb shell? But without support from scala core developers – it will be useless.
PS “As of December 2011 there are over 700,000 Android devices activated every day.” It is very disappoint that scala developers ignore such part of market and build compiler in unportable way, that allow to use cross platform language only at limited number of targets.
I/dalvikvm( 282): Could not find method
scala.actors.IScheduler.getClass, referenced from method
scala.actors.scheduler.DaemonScheduler$.makeNewScheduler
W/dalvikvm( 282): VFY: unable to resolve interface method 1527:
Lscala/actors/IScheduler;.getClass ()Ljava/lang/Class;
How "should I fix it regardless?" :-) My ability to knowledge
everything is a bit limited. I don't know internal mechanic of scala
compiler. But I may regardless if needed with help of someone.
Let me ask, latest git copy build properly at your environment if you
replace lib/scala* with latest?
IMHO The problem is to find someone that would clear bugs from scala
code. If there someone from scala development team I will help him
with great pleasure.
I finally found time to do another proper test and it seems that at
least the example code from SI-4620 now works with the latest snapshot
(scala-compiler-2.10.0-20120105.025731-245.jar).
I checked the resource consumption with my logging dalvikvm and the
test app now seems to use only 4MB of LinearAlloc memory which is
under the current limit of 5MB. In newer versions of Android (> 4)
this limit has been increased to 8 MB so there should be some buffer
space for the next time.
I assume it was your fix which decreased resource consumption to this
level. So thanks again!
Johannes
Here's the explaining comment from the sources:
/*
* Someday, retrieve the linear alloc struct associated with a particular
* class loader. For now, always use the boostrap loader's instance.
*/
[1] https://github.com/android/platform_dalvik/blob/master/vm/LinearAlloc.cpp#L87
1.) The dex-file binary format can only handle 65k methods. This is
what could be handled by multiple dex files. This is currently worked
around by using proguard or by pre-installing the Scala libraries to
the developer phone.
http://code.google.com/p/android/issues/detail?id=20814
2.) A deep interface hierarchy can lead to excessive LinearAlloc use
in dalvik vm. Scala's collection library has quite a "deep interface
hierarchy" and triggered this problem. The situation will be improved
on the Scala side by omitting redundant interface declarations (Scala
trunk version is already much better in this regard). Maybe this will
improved on the Dalvik side if the proposed fix will be accepted.
http://code.google.com/p/android/issues/detail?id=22586
3.) The problem Alexey reported earlier in this thread where in a
former Scala 2.10-SNAPSHOT version an `invokeinterface` bytecode is
generated for calls to methods defined in `java.lang.Object` for some
cases
which works in Hotspot but fails in Dalvik. This is now fixed in Scala.
Johannes
IMHO I find one more problem place.
I/dalvikvm( 618): Could not find method
sun.misc.Unsafe.throwException, referenced from method
scala.concurrent.forkjoin.ForkJoinTask.rethrowException
W/dalvikvm( 618): VFY: unable to resolve virtual method 26641: Lsun/
misc/Unsafe;.throwException (Ljava/lang/Throwable;)V
D/dalvikvm( 618): VFY: replacing opcode 0x6e at 0x0004
https://github.com/jrudolph/scala-android-libs/issues/3
Can you try that and report back?
Johannes
--
Did you test this solution, Alexey?
I don't think it will work since it looks like this being a
verification problem. Apache Harmony seems to be missing
Unsafe.throwException altogether. If setting the property alone isn't
working can you try removing the complete "scala.concurrent.forkjoin"
package from your Scala jar?