spark-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Imran Rashid (JIRA)" <>
Subject [jira] [Commented] (SPARK-11583) Make MapStatus use less memory uage
Date Thu, 12 Nov 2015 22:30:11 GMT


Imran Rashid commented on SPARK-11583:

[~lemire] I thought Kent Yao's analysis was pretty reasonable (with a few additional suggestions
I'll make below).  But it sounds like that isn't what you were expecting -- can you suggest
what else you have in mind?  I think it would be better to do the same thing directly on the
bitsets, without the additional complexity from spark in the middle, but in general that is
what I was looking for.  The truth of the matter is that as Spark is meant to be very general
purpose, we really can't say anything specific about what the data in these bitsets will be.
 They might be very full; they might be very dense;  there isn't any particular reason to
suspect that they'd be organized into runs (more than you'd expect by random chance).  I understand
that one format won't be better in all cases, but what I'm looking for is to to find the format
which works well for a wide range of loads, *and* that doesn't contain too big a penalty in
the worst case.  Eg., if the most memory-intensive cases use 20% more memory in roaring than
a plain bitset, that is strong evidence against roaring, even if its much better in other
cases.  OTOH, if its 1% in those cases, and 50% better in others, then we should probably
still go with roaring.  From the analysis I did above, it was less than 1% overhead for alternating
bits, which I thought would be the worst case.  Are there other cases you think are important
to look at in particular?

[~Qin Yao] thanks so much for that analysis.  That seems to agree with our expectations from
the analysis above.  The one case in which the roaring bitmap is much worse can be explained
by the lack of a call to {{runOptimize}}.  

Can I ask you take it your analysis a step further?
(a) use roaring bitmap 0.5.10
(b) I think we'd be better of if you just looked at the bitsets directly, rather than going
through spark.  First of all, its kind of confusing to talk about dense outputs from spark
leading to sparse bitmaps b/c the code uses empty 
(c) Given Daniel's explanation above of {{runOptimize}}, can you be sure to call {{runOptimize}}
after adding all the bits to the roaring bitmap?  That would be the equivalent of adding it
here to the spark 1.5 code.
(d) Just to eliminate any doubts -- can you see the memory usage from roaring bitmap with
the bits reversed?  I understand that it *should* be the same, but might as well double check.
(e) can you add a case for alternating bits (and whatever else Daniel suggests for worst cases)?

In my mind, that should settle things.  It would be great to have the code for that analysis
attached here if possible, if we ever revisit it.  I have every reason to believe this will
confirm that we should be using Roaring (with a call to {{runOptimize}} added), but lets just
make the case very clear.

> Make MapStatus use less memory uage
> -----------------------------------
>                 Key: SPARK-11583
>                 URL:
>             Project: Spark
>          Issue Type: Improvement
>          Components: Scheduler, Spark Core
>            Reporter: Kent Yao
> In the resolved issue, as I said, using
BitSet can save ≈20% memory usage compared to RoaringBitMap. 
> For a spark job contains quite a lot of tasks, 20% seems a drop in the ocean. 
> Essentially, BitSet uses long[]. For example a BitSet[200k] = long[3125].
> So if we use a HashSet[Int] to store reduceId (when non-empty blocks are dense,use reduceId
of empty blocks; when sparse, use non-empty ones). 
> For dense cases: if HashSet[Int](numNonEmptyBlocks).size <   BitSet[totalBlockNum],
I use MapStatusTrackingNoEmptyBlocks
> For sparse cases: if HashSet[Int](numEmptyBlocks).size <   BitSet[totalBlockNum],
I use MapStatusTrackingEmptyBlocks
> sparse case, 299/300 are empty
> sc.makeRDD(1 to 30000, 3000).groupBy(x=>x).top(5)
> dense case,  no block is empty
> sc.makeRDD(1 to 9000000, 3000).groupBy(x=>x).top(5)

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message