# A Vision of the Intelligent Piano of the Future

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Next Generation of Pianos

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Future of Pianos

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# Making Pianos Intelligent

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Supportive Piano of the Future

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Intelligent Piano of the Future

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Human-Centered Piano of the Future

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Vision of a Human-Centered Piano of the Future

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

# The Vision of a Human-Centered Piano

Jordan Aiko Deja  0001-9341-6088 University of PrimorskaKoperSlovenia6000 De
La Salle UniversityManilaPhilippines<EMAIL_ADDRESS>,  Sven Mayer
LMU MunichMunichGermany<EMAIL_ADDRESS>,  Klen Čopič Pucihar  University
of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>and  Matjaž Kljun
University of PrimorskaKoperSlovenia6000<EMAIL_ADDRESS>
(2022)

###### Abstract.

For around 300 years, humans have been learning to play the modern piano
either with a teacher or on their own. In recent years teaching and learning
have been enhanced using augmented technologies that support novices. Other
technologies have also tried to improve different use cases with the piano,
such as composing and performing. Researchers and practitioners have showcased
several forms of augmentation, from hardware improvements, sound quality,
rendering projected visualizations to gesture-based and immersive
technologies. Today, the landscape of piano augmentations is very diverse, and
it is unclear how to describe the ideal piano and its features. In this work,
we discuss how the human-centered piano – the piano that has been designed
with humans in the center of the design process and that effectively supports
tasks performed on it – can support pianists. In detail, we present the three
tasks of learning, composing, and improvising in which a human-centered piano
would be beneficial for the pianist.

piano, human-centered design, intelligent music interface, music interface

††copyright: ccbysa††journalyear: 2022††conference: Intelligent Music
Interfaces: When Interactive Assistance and Augmentation Meet Musical
Instruments; April 30, 2022; New Orleans, LA††booktitle: Intelligent Music
Interfaces: When Interactive Assistance and Augmentation Meet Musical
Instruments, April 20, 2022,New Orleans, LA††isbn: ††ccs: Human-centered
computing Human computer interaction (HCI)††ccs: Human-centered computing
Interaction devices††ccs: Applied computing Sound and music computing††ccs:
Applied computing Interactive learning environments

##  1\. Introduction

Bartolomeo Cristofori designed the first piano in the 1700s deriving it from
the clavichord and harpsichords (Pollens et al., 1995). The piano generates
sounds using hammers (controlled by a keyboard) striking strings. The initial
piano implementation has been evaluated and reviewed to address various issues
or improve the experience in general. For instance, dimensions and
measurements were standardized for supporting proper posture while playing the
piano. However, further research has observed that these measurements may not
be as inclusive and may be gender-biased. To address this, physical
augmentations have been introduced instead to accommodate users with specific
needs (e.g., adding a seat riser for shorter people, adding a cushion for
comfort during prolonged usage). Other physical appendages and digital
hardware (e.g. magnetic resonators, actuators (McPherson, 2010), string
actuation for key sensing (McPherson and Kim, 2010), sensors for pitch control
(McPherson et al., 2013)) have also been introduced to improve sound quality
or introduce a different listening experience. Beyond the listening
experience, augmentations have also been done to serve disparate set of use-
cases in the piano. They come in either digital, electronic or acoustic
augmentation.

Figure 1. A human-centered piano intelligently understands the contexts behind
each task of a pianist: learner, composer, performer.

A human-centered piano intelligently understands the contexts behind each task
of a pianist: learner, composer, performer.

Generally, an augmentation is initially introduced to the piano to serve a
specific purpose. For instance, electronic augmentations (e.g., audio jack or
a MIDI interface) have been added to allow the piano to be listened to by
large crowd or by oneself. For example, to accommodate large audiences during
events such as recitals, concerts, or orchestras, the piano has to be
connected to a sound system. If a pianist wants to listen to their work
privately, they can listen to a recording of their own practice on the
headphones. Recording, playing back music and post-processing with filters
became possible too with these augmentations. At present, these augmentations
appear minor or standard since they are now part of consumer-based electronic
pianos.

With recent technological innovations such as the internet, artificial
intelligence, and mixed reality, designers have further reshaped the piano and
music listening experience (Deja et al., 2020). Just within the recent two
decades, we have seen a wave of digital piano augmentations that cater to
different use-cases and tasks: (i) vision-based algorithms are used to detect
proper posture and proper movement (Huang et al., 2011) (which we have also
seen for other instruments such as violin (Van Der Linden et al., 2010) and
guitar (Marky et al., 2021; Shin et al., 2018)), (ii) augmented visualizations
have been overlaid to help learners with timing and which keys to press (Weing
et al., 2013); (iii) gamified, practice and other modules have been introduced
to motivate learners (Rogers et al., 2014) and (iv) other interactions have
been introduced to encourage users to improvise (Karolus et al., 2020; Deja,
2021b, a). Whether these innovations have been very effective for their
specific purpose warrants further investigation.

What is known is that the piano has always been designed and created for the
user taking various roles. A novice (learner) learns the piano with the
guidance of a mentor (teacher). A pianist performs in front of an audience –
(performer). In the midst of such performance, a pianist may improvise –
(improviser). A person composes a song and arranges it with the use of the
piano – (composer). While taking on one of these roles, users may have their
own styles and systems to successfully accomplish their task.

As users typically experience pain points and problems when doing these tasks
(teaching, learning, performing, improvising, composing) (Chan et al., 2019),
technological innovations were introduced to potentially help them. However,
newer innovations introduce newer affordances and issues with its use (Dede,
1996), which we argue is a never-ending problem with technology. Additionally,
not many features introduced by these innovations have been shipped as
consumer-based features so far. To meet halfway, the existing use-cases in
piano and the augmentations introduced to address the pain points users
encounter along the way, we present our position towards a smart piano – the
human-centered piano of the future. We present different use-cases known (in
the present) and emerging that we think may benefit from piano augmentation.
We argue that such design may provide a more precise direction in the design
and development of the piano of the future.

##  2\. The Human-Centered Piano

The piano is used somehow differently by users coming from various proficiency
levels. A piano is a tool used to practice consistently by a novice or a
beginner user. A more experienced pianist still trains with it but on a
different cadence and intensity. They use the piano to practice for a
performance (such as recitals or concerts) or to help them when composing new
music. They may use the piano to record a performance, a melody or create
unique arrangements. For both types of users, such tasks entail a lot of
practice or trial-and-error activities. However, the depth in usage varies and
is affected by other factors. Learning, though considered a personal activity,
is usually a procedure that a mentor or teacher typically observes. Composing
is either an activity done alone or in collaboration (if one has to play with
others such as in a band, or a producer or sound engineer). During
performances, the usage may involve certain constraints.

There is less pressure to make mistakes in front of a teacher during a
teaching session than the amplified pressure a performer feels during a public
performance. Improvising during a performance requires that the performer
exhibits a solid mastery of music theory to produce musically sound and valid
melodies. In terms of recording a composition, a musician should have practice
their piece so the recording process becomes smooth and have lesser mistakes
or trials. Overall, while all these involve the use of the piano, many factors
are treated differently depending on each task. These include: (i) the ease of
using the piano; (ii) the needed level of concentration during play; (iii) the
confidence of the user during these activities; (iv) the cognitive load and
other physiological factors experienced by the user. As such, we need to
introduce intelligent interventions that appeal to the different needs of
these users. In the succeeding sections, we present how we envision some
human-centered augmentations.

###  2.1. Learning

There are several known methods for learning the piano such as Kodaly (Howard,
1996) Dalcroze (Mead, 1994), Orff (Shamrock, 1997) and Suzuki (Comeau, 2012).
These were implemented and have been augmented differently based on several
learning frameworks and theories (Bandura and Walters, 1977; Kolb, 2014).
Generally, a piano learner spends a significant amount of time practicing,
assessing their work and asking for support from the teacher. Self-reflection
(Zimmerman and Moylan, 2009) has been documented to help and motivate students
as well.

Since learning the piano is usually a long and tedious process, the experience
must be enriched to allow learners to be reflective, motivated and engaged.
The ideal human-centered piano should enable learners to record their training
sessions and reflect on them. Learners should be able to highlight specific
segments in their practice recordings and seek support based on their
performance. Constant recommendations regarding posture and body
synchronization should be detected and provided to the learner, especially
when a teacher is absent. The system should be able to capture and understand
learners’ current physiological state and use this information to manage their
cognitive load. If possible, it should be captured in the most unobtrusive way
possible without being compromised by noise. The captured data should be also
used to manage the augmentations presented to the learner at a given time
(e.g. bpm of overlaid piano roll visualizations, quantity and size of
visualizations of keys that need pressing).

While several of these features may have appeared in some prototypes published
through the years, an ideal human-centered piano combines these and tackles
the piano learning problem similar to that of learning a language or riding
bike. Learners learns better the more they use the piano and build on the
over-all experience.

###  2.2. Composing

Music composition is summed up in three main activities: ideation, sketching
and revision (Bennett, 1976). When composing for the piano, a musician usually
comes up with some notes and chords in segments. They write these notes with a
pen and then switch to playing these keys on the piano to hear how it would
sound. They begin with an initial sketch and cumulatively build on it. During
this process they would switch between write something on paper and then
playing it in the piano. This process repeats until they are satisfied. Or, in
some instances, they would start over again. Mechanically, this process
involves shifting from one task to another during the process – from holding a
writing tool for composing to pressing the piano keys and turning back.

Based on the findings from (Chan et al., 2019), this usually leads to a loss
of momentum or the musician’s equivalent of a writer’s block, especially for
novices. In such scenarios, it would be ideal to have an AI agent that aids
the musician in composing their piece without overtaking their tastes and
appealing to their styles. This has been seen in some works (Numao et al.,
2002; Legaspi et al., 2007; Deja et al., 2018) on emotion-based music systems
as well. AI agents should not replace musicians but rather provide them with
an augmented music composition process that makes them better in their work. A
self-learning empathy framework can be incorporated in an human-centered piano
to model, understand and then recommend musical hints to the composer (in the
form of new keys, chords, motifs or segments). This can be achieved by
integrating emotion detection techniques and utilizing existing computer-aided
composition approaches. A human-centered piano should be equipped with sensors
and other input modalities that would allow it to model, understand and build
recommendations that would be personalized for a composer’s styles and tastes.

###  2.3. Improvising

A smart piano can have an AI agent that can collaborate with the user during
composition and the actual performances. This is most important when a piano
user improvises during a performance. Piano improvisation can often be
regarded as a more advanced form of composition since the process takes place
in play-time (playing the piano in real-time and not during practice).
Improvisers perform not only the traditional melody defined in a sheet
notation but use additional chords and/or melody that they think would make
the piece more enjoyable or sound aesthetically different.

Based on music theory, certain chords and progressions go along together to
create multiple or more harmonious melodies. Some combinations are not
musically sound but still aurally acceptable (if assessed with quality of
hearing output alone). This makes improvisation difficult to assess (Deja,
2021b) and augment. Like in composition, a human-centered piano should be a
companion that the piano user can jam and “collaborate” with during a
performance. This can be achieved by a piano that accepts inputs of different
forms and modalities (such as physiological signals, spatiotemporal movement
data, etc). For instance, it can be a gesture-based agent (Karolus et al.,
2020) that understands the free flowing movement of the arms of the piano user
much like dancing while performing and generating a sub melody in the process.
It can be adaptive and dynamic that understands the individual taste of the
user and then produce an impro piano roll helping the user to jazz-ify the
piece being played. It can also be an intelligent agent that lets the piano
performer freely play their improvisation melody, records it and later on
generates a reverse-piano roll that the performer can save (and then review).
This process would allow performers to evaluate and assess if their
improvisation is musically sound based on music theory and rules.
Additionally, the performers would broaden their musical vocabulary while
getting intelligent feedback on their improvisation.

##  3\. Discussion

We based the above presented visions of the human-centered piano with the
ulterior goal of elevating the piano from a tool to a companion. From the
initial design of the piano, we have seen how different it is now. We
introduce newer ways of interacting with the piano as we transition from
simply producing a sound to recreating an existing masterpiece into a remixed
symphony. We believe that the features we presented may represent that of a
Human-Centered piano, however this is subject to further exploration and
validation with actual users. We also posit that some benefits and
disadvantages go with it as well.

Experts and scholars argue that one essential component in piano playing is
not losing its human touch (Schubert et al., 2017). As most compositions and
pieces come from authentic human emotion, expressions and experiences, it is
difficult to ignore that artificially generated motifs sequences may miss this
vital component. This is why the human-centered piano must attempt to become a
companion of the performer or composer and not entirely replace them.

It will also be equally challenging to ensure that a user’s unique identity
(similar to how a piece can be uniquely classified as a work by Bach or
Chopin) is not lost and merged with the shared repository of recommendations
when used on a massive scale. For example, two talented performers must be
able to use the human-centered piano and improve their musical vocabulary and
at the same time have their work and performance easily distinguishable from
each other.

Automatically-generated and emotion-inspired hints presented may have certain
benefits as well. Piano users either spend less time in a musician’s block
when they receive tips or may be overwhelmed by the number of ideas. The
proper timing and quantity of these hints must not overwhelm the user, and can
be discovered through adequate user tests.

In the design of an human-centered piano, we factored in several modalities
and parameters such as physiological data, motion data, personal data
describing tastes and preferences. Security and privacy must be strictly-
upheld in all these conditions. As we factor in more considerations in the
design of this piano of the future, we introduce more benefits and issues with
them. We posit that the piano of the future must always consider a holistic
approach of the user: the learner, teacher, composer, performer and
collaborator.

##  4\. Summary

We revisited the brief history of pianos and piano augmentation in this work.
We drew inspiration for features of what would be an ideal human-centered
piano. We looked at different activities, and use-cases musicians do with the
piano and the augmentations that have been introduced with it. These
activities and use-cases looked at piano users from different levels, namely
students (as beginners), composers (as experienced users), and those who
improvise (as even more advanced). We analyzed these critical points and
identified how current or emerging technologies could be further developed
towards a long-lasting design. Finally, we argue that a human-centered piano,
designed towards the known use-cases at hand, would be an appropriate argument
for the intelligent piano of the future.

## References

  * (1)
  * Bandura and Walters (1977) Albert Bandura and Richard H Walters. 1977.  _Social learning theory_. Vol. 1.  Prentice-hall Englewood Cliffs, NJ, Englewood Cliffs New Jersey.
  * Bennett (1976) Stan Bennett. 1976\.  The process of musical creation: Interviews with eight composers.  _Journal of research in music education_ 24, 1 (1976), 3–13.
  * Chan et al. (2019) Kevin Gray Chan, Jordan Aiko Deja, John Patrick Tobias, Allen Vincent Gonzales, and Migo Andres Dancel. 2019.  Applying User-Centered Techniques in the Design of a Usable Mobile Musical Composition Tool. In _Proceedings of the 5th International ACM In-Cooperation HCI and UX Conference_ (Jakarta, Surabaya, Bali, Indonesia) _(CHIuXiD’19)_. Association for Computing Machinery, New York, NY, USA, 152–159.  https://doi.org/10.1145/3328243.3328263
  * Comeau (2012) Gilles Comeau. 2012\.  Playing by ear in the Suzuki Method: Supporting evidence and concerns in the context of piano playing.  _The Canadian Music Teacher, årg_ 62 (2012), 42.
  * Dede (1996) Chris Dede. 1996\.  The evolution of distance education: Emerging technologies and distributed learning.  _American Journal of Distance Education_ 10, 2 (1996), 4–36.  https://doi.org/10.1080/08923649609526919
  * Deja (2021a) Jordan Aiko Deja. 2021a.  Adaptive Visualisations Using Spatiotemporal and Heuristic Models to Support Piano Learning. In _Proceedings of the 29th ACM Conference on User Modeling, Adaptation and Personalization_. Association for Computing Machinery, New York, NY, USA, 286–290.  https://doi.org/10.1145/3450613.3459656
  * Deja (2021b) Jordan Aiko Deja. 2021b.  Encouraging Improvisation in Piano LearningUsing Adaptive Visualisations and Spatiotemporal Models. In _Adjunct Publication of the 23rd International Conference on Mobile Human-Computer Interaction_. Association for Computing Machinery, New York, NY, USA, Article 24, 4 pages.  https://doi.org/10.1145/3447527.3474865
  * Deja et al. (2020) Jordan Aiko Deja, Nuwan Attygale, Klen Copic Pucihar, and Matjaz Kljun. 2020.  Sound 2121: Cross-Reality Transitions Between Real and Augmented Sound Landscape. In _International Workshop on Cross-Reality (XR) Interaction 2020_. CEUR Workshop Proceedings, Lisbon, Portugal, 1–4.  http://ceur-ws.org/Vol-2779/paper2.pdf.
  * Deja et al. (2018) Jordan Aiko Deja, Rafael Cabredo, and Toni-Jan Keith Monserrat. 2018\.  On Building an Emotion-Based Music Composition Companion. In _Proceedings of the Asian HCI Symposium’18 on Emerging Research Collection_ (Montreal, QC, Canada) _(Asian HCI Symposium’18)_. Association for Computing Machinery, New York, NY, USA, 25–28.  https://doi.org/10.1145/3205851.3205859
  * Howard (1996) Priscilla M Howard. 1996\.  Kodaly Strategies for Instrumental Teachers: When the Kodály method is extended to string and other instrumental instruction, it offers opportunities for enhancing student musicianship.  _Music Educators Journal_ 82, 5 (1996), 27–33.  https://doi.org/10.2307/3398929
  * Huang et al. (2011) Feng Huang, Yu Zhou, Yao Yu, Ziqiang Wang, and Sidan Du. 2011.  Piano ar: A markerless augmented reality based piano teaching system. In _2011 Third international conference on intelligent human-machine systems and cybernetics_ , Vol. 2. IEEE, Hangzhou, China, 47–52.  https://doi.org/10.1109/IHMSC.2011.82
  * Karolus et al. (2020) Jakob Karolus, Annika Kilian, Thomas Kosch, Albrecht Schmidt, and Paweł W. Wozniak. 2020\.  Hit the Thumb Jack! Using Electromyography to Augment the Piano Keyboard. In _Proceedings of the 2020 ACM Designing Interactive Systems Conference_. Association for Computing Machinery, New York, NY, USA, 429–440.  https://doi.org/10.1145/3357236.3395500
  * Kolb (2014) David A Kolb. 2014\.  _Experiential learning: Experience as the source of learning and development_.  FT press, Kaunnanakai, Hawaii.
  * Legaspi et al. (2007) Roberto Legaspi, Yuya Hashimoto, Koichi Moriyama, Satoshi Kurihara, and Masayuki Numao. 2007\.  Music compositional intelligence with an affective flavor. In _Proceedings of the 12th international conference on Intelligent user interfaces_. ACM Digital Library, Hawaii, USA, 216–224.
  * Marky et al. (2021) Karola Marky, Andreas Weiß, Andrii Matviienko, Florian Brandherm, Sebastian Wolf, Martin Schmitz, Florian Krell, Florian Müller, Max Mühlhäuser, and Thomas Kosch. 2021.  Let’s Frets! Assisting Guitar Students During Practice via Capacitive Sensing. In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ (Yokohama, Japan) _(CHI ’21)_. Association for Computing Machinery, New York, NY, USA, Article 746, 12 pages.  https://doi.org/10.1145/3411764.3445595
  * McPherson (2010) Andrew McPherson. 2010\.  The magnetic resonator piano: Electronic augmentation of an acoustic grand piano.  _Journal of New Music Research_ 39, 3 (2010), 189–202.  https://doi.org/10.1080/09298211003695587
  * McPherson et al. (2013) Andrew P McPherson, Adrian Gierakowski, and Adam M Stark. 2013\.  The space between the notes: adding expressive pitch control to the piano keyboard. In _Proceedings of the SIGCHI conference on human factors in computing systems_. ACM Digital Library, Paris, France, 2195–2204.
  * McPherson and Kim (2010) Andrew P McPherson and Youngmoo E Kim. 2010.  Augmenting the Acoustic Piano with Electromagnetic String Actuation and Continuous Key Position Sensing.. In _NIME_. Proceedings of NIME, Sydney, Australia, 217–222.
  * Mead (1994) Virginia H. Mead. 1994\.  _Dalcroze Eurhythmics in Today’s Music Classroom_.  Schott, Georgia USA.
  * Numao et al. (2002) Masayuki Numao, Shoichi Takagi, and Keisuke Nakamura. 2002\.  Constructive adaptive user interfaces-composing music based on human feelings. In _Proceedings of the National Conference on Artificial Intelligence_. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, American Association for Artificial Intelligence, Edmonton Alberta Canada, 193–198.
  * Pollens et al. (1995) Stewart Pollens, Pollens Stewart Pollens, John Butt, et al. 1995\.  _The early pianoforte_.  Cambridge University Press, New York, USA.
  * Rogers et al. (2014) Katja Rogers, Amrei Röhlig, Matthias Weing, Jan Gugenheimer, Bastian Könings, Melina Klepsch, Florian Schaub, Enrico Rukzio, Tina Seufert, and Michael Weber. 2014\.  P.I.A.N.O.: Faster Piano Learning with Interactive Projection. In _Proceedings of the Ninth ACM International Conference on Interactive Tabletops and Surfaces_ (Dresden, Germany) _(ITS ’14)_. Association for Computing Machinery, New York, NY, USA, 149–158.  https://doi.org/10.1145/2669485.2669514
  * Schubert et al. (2017) Emery Schubert, Sergio Canazza, Giovanni De Poli, and Antonio Rodà. 2017.  Algorithms can mimic human piano performance: the deep blues of music.  _Journal of New Music Research_ 46, 2 (2017), 175–186.
  * Shamrock (1997) Mary Shamrock. 1997\.  Orff-Schulwerk: An Integrated Foundation: This article on the methodologies and practices of Orff-Schulwerk was first published in the Music Educators Journal in February 1986.  _Music Educators Journal_ 83, 6 (1997), 41–44.
  * Shin et al. (2018) Yejin Shin, Jemin Hwang, Jeonghyeok Park, and Soonuk Seol. 2018\.  Real-Time Recognition of Guitar Performance Using Two Sensor Groups for Interactive Lesson. In _Proceedings of the Twelfth International Conference on Tangible, Embedded, and Embodied Interaction_ (Stockholm, Sweden) _(TEI ’18)_. Association for Computing Machinery, New York, NY, USA, 435–442.  https://doi.org/10.1145/3173225.3173235
  * Van Der Linden et al. (2010) Janet Van Der Linden, Erwin Schoonderwaldt, Jon Bird, and Rose Johnson. 2010.  Musicjacket—combining motion capture and vibrotactile feedback to teach violin bowing.  _IEEE Transactions on Instrumentation and Measurement_ 60, 1 (2010), 104–113.
  * Weing et al. (2013) Matthias Weing, Amrei Röhlig, Katja Rogers, Jan Gugenheimer, Florian Schaub, Bastian Könings, Enrico Rukzio, and Michael Weber. 2013.  P.I.A.N.O.: Enhancing Instrument Learning via Interactive Projected Augmentation. In _Proceedings of the 2013 ACM Conference on Pervasive and Ubiquitous Computing Adjunct Publication_ (Zurich, Switzerland) _(UbiComp ’13 Adjunct)_. Association for Computing Machinery, New York, NY, USA, 75–78.  https://doi.org/10.1145/2494091.2494113
  * Zimmerman and Moylan (2009) Barry J Zimmerman and Adam R Moylan. 2009.  Self-regulation: Where metacognition and motivation intersect.  In _Handbook of metacognition in education_. Routledge, New York, USA, 311–328.


#  DJXPerf: Identifying Memory Inefficiencies via Object-centric Profiling for
Java

Bolun Li  North Carolina State University<EMAIL_ADDRESS>,  Pengfei Su
University of California, Merced<EMAIL_ADDRESS>,  Milind Chabbi  Scalable
Machines Research<EMAIL_ADDRESS>,  Shuyin Jiao  North Carolina
State University<EMAIL_ADDRESS>and  Xu Liu  North Carolina State University
<EMAIL_ADDRESS>
(2018)

###### Abstract.

Java is the “go-to” programming language choice for developing scalable
enterprise cloud applications. In such systems, even a few percent CPU time
savings can offer a significant competitive advantage and cost saving.
Although performance tools abound in Java, those that focus on the data
locality in the memory hierarchy are rare.

In this paper, we present DJXPerf, a lightweight, object-centric memory
profiler for Java, which associates memory-hierarchy performance metrics
(e.g., cache/TLB misses) with Java objects. DJXPerf uses statistical sampling
of hardware performance monitoring counters to attribute metrics to not only
source code locations but also Java objects. DJXPerf presents Java object
allocation contexts combined with their usage contexts and presents them
ordered by the poor locality behaviors. DJXPerf’s performance measurement,
object attribution, and presentation techniques guide optimizing object
allocation, layout, and access patterns. DJXPerf incurs only $\sim$8% runtime
overhead and $\sim$5% memory overhead on average, requiring no modifications
to hardware, OS, Java virtual machine, or application source code, which makes
it attractive to use in production. Guided by DJXPerf, we study and optimize a
number of Java and Scala programs, including well-known benchmarks and real-
world applications, and demonstrate significant speedups.

compiler techniques and optimizations, performance, dynamic analysis, managed
languages and runtimes

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Software and its engineering
Compilers††ccs: Software and its engineering General programming languages

##  1\. Introduction

Java is the “go-to” programming language choice for developing scalable
enterprise cloud applications (javagoto; twitterjava; twitterjava2; hotjava;
googlejava; netflixjava; uberava). Performance is critical in such Java
programs running on a distributed system comprised of thousands of hosts; on
such systems, saving CPU time even by a few percentages offers both
competitive advantages (lower latency) and cost savings. Tools abound in Java
for “hotspot” performance analysis that can bubble-up code contexts where the
execution spends the most time and are also used by developers for tuning
performance. However, once such “low hanging targets” are optimized,
identifying further optimization opportunities is not easy. Java, like other
managed languages, employs various abstractions, runtime support, just-in-time
compilation, and garbage collection, which hide important execution details
from the plain source code.

In modern computer systems, compute is “free” but memory accesses cost dearly.
Long-latency memory accesses are a major cause of execution stalls in modern
general-purpose CPUs. CPU’s memory hierarchy (different levels of caches)
offers a means to reduce average memory access latency by staging data into
caches and repeatedly accessing before evicting. Access patterns that reuse
previously fetched data are said to exhibit good data locality. There are
traditionally two types of data locality: spatial and temporal. An access
pattern exhibits spatial locality when it accesses a memory location and then
accesses nearby locations soon afterward. An access pattern exhibits temporal
locality when it accesses the same memory multiple times. Programs that do not
exploit these features are said to lack spatial or temporal locality.

Maintaining the locality of references in a CPU’s memory hierarchy is well-
known and mastered to achieve high performance in natively compiled code such
as C and C++. Besides the traditional locality problems, garbage collected
languages such as Java expose another unique locality issue — memory bloat
(Reusable). Memory bloat occurs by allocating (and initializing) many objects
whose lifetimes do not overlap. For example, allocating objects in a loop
where the lifetime of the object is only the scope of the loop body. Since the
garbage collection happens sometime later in the future, the memory
consumption spikes, which results in a higher memory footprint and suboptimal
cache utilization. Memory bloat can be seen as a case of lack of both spatial
and temporal locality because accessing a large number of independent objects
results in accessing disparate cache lines and little or no reusing of a
previously accessed cache line(s).

Figure 1. Code-centric vs. object-centric profiling. $O$ denotes an object and
$I$ denotes a memory access instruction; tuple $\langle O_{m},I_{n}\rangle$
denotes that instruction $I_{n}$ accesses object $O_{m}$.

Exploring data locality in native languages has been under investigation for
decades. There exist a number of tools (ibs-cgo; ibs-pact; ibs-ispass; ibs-sc;
DBLP:conf/sigmetrics/BergH05; SLO1; SLO2; reuse-chen;
Liu:2015:STI:2807591.2807648) to measure the data locality using various
metrics. Software metrics such as reuse distances (Zhong:2008; time-reuse;
tree-compression; reuse-chen; macpo), memory footprints (footprints;
chunking), and cache miss ratio curves (SLO1;
CaBetacaval:2003:ECM:782814.782836), which are derived from memory access
traces, quantify the locality independent of architectures. In contrast,
hardware metrics, such as cache/TLB misses, collected with hardware
performance monitoring units (PMU) during program execution, quantify data
locality on a given architecture. Attributing PMU metrics to source code is a
straightforward way to demonstrate code regions that incur high access
latencies; we call it as _code-centric profiling_.

In object-oriented systems, delivering profiles centered around objects is
highly desirable. An object may have accesses to it scattered in many places,
and each code location may contribute a small fraction to the overall data-
access problem. Bridging the memory-hierarchy latency metrics with runtime
data objects requires more involved measurement and attribution techniques,
which is the focus of our work; we call it as _object-centric profiling_. Note
that _object-centric profiling_ not only shows the objects subject to high
aggregate access latencies but also pinpoints code locations ordered by their
contribution to the overall latency to the object under question.

Figure 1 illustrates the difference between code-centric profiling and object-
centric profiling. The code-centric profiling associates the cache miss metric
with memory accesses, showing that access $I_{c}$ accounts for most cache
misses during program execution. In contrast, the object-centric profiling
aggregates the cache miss metric from different accesses that touch the same
object to present a unified view. Guided by the object-centric profiling, we
find that object $O_{1}$ accounts for most cache misses. However, its accesses
are scattered across multiple instructions, and each individual access is less
significant than the access to object $O_{3}$. Thus, instead of checking
individual accesses, one can apply various optimization to the allocation of
the $O_{1}$ object or its data layout.

Collecting object-centric profiles for Java has unique challenges posed by
managed runtimes. First, just-in-time compilation and interpretation used in
JVM disjoin the program source code and its execution behaviors. Second,
automatic runtime memory management (i.e., garbage collection) further impedes
understanding memory performance of Java and other languages based on JVM,
such as Scala (scala-www) and Clojure (clojure-www).

Since developers in native languages have explicit knowledge and understanding
of objects and their lifetimes, they pay more attention to objects and their
locality; Java developers, on the other hand, lack the precise knowledge of
object lifetimes and their influence on locality. Surprisingly, Java lacks any
object-centric performance attribution tool, which can pinpoint objects
subject to serious latency problems. Tools such as Linux perf (perf) and Intel
VTune (Intel:VTune) exploit hardware performance monitoring and attribute
cache miss metrics to code, such as Java methods, loops, or source locations,
but they do not attribute metrics to Java objects. As shown in Figure 1, these
tools only attribute metrics to problematic code lines; without object-level
information, they cannot tell which objects are problematic and deserve
optimization. A few tools such as (Fourtrends; XuThesis; Softwarebloat)
instrument Java byte code to identify problematic objects. However, these
tools suffer from high overhead and lack real execution performance metrics
available from the hardware. Often times, the optimization lacking the
quantification from the underlying hardware can yield trivial or negative
speedups (ibs-ispass).

Most of today’s shared memory multiprocessor systems support non-uniform
memory access (NUMA), where the loss of data locality not only pervasively
exists within a single CPU processor (aka a NUMA socket), but also across CPU
processors. NUMA characteristics introduce the explicit NUMA property of the
shared memory systems, where differences in local and remote memory access
latencies can be up to two orders of magnitude. Shared memory applications
with transparent data distributions across all nodes often incur high
overheads due to excessive remote memory accesses. Minimizing the number of
remote accesses is crucial for high performance, and this, in turn, usually
requires a suitable, application-specific data distribution. In general,
choosing an appropriate data distribution remains a challenge. We can
attribute metrics to individual objects with the object-centric idea, then
identifying the objects that suffer from severe remote accesses.

In this paper, we describe DJXPerf, a lightweight object-centric profiler for
Java programs. DJXPerf complements existing Java profilers by collecting
memory-related performance metrics from hardware PMUs and attributing them
with Java objects. DJXPerf provides unique insights into Java’s memory
locality issues. In the rest of this section, we show two motivating examples,
the contribution of this paper and the paper organization.

###  1.1. Motivating Examples

In this section, we motivate the importance of combining object-level
information and PMU metrics for locality optimization. Listing 1 and 2 show
two problematic code snippets suffering from memory bloat, which are
respectively from batik and lusearch, both from Dacapo-9.12 (dacapo). We run
them with the default large inputs using $48$ threads.

In Listing 1, the object allocation site at line 5 creates an array of float
objects in the method makeRoom, which is part of the class
ExtendedGeneralPath. This allocation site is repeatedly invoked $2478$ times,
resulting in memory bloat. For optimization, one can move the array allocation
outside of the loop that encloses the method makeRoom and replace it with a
static object array, aka the singleton pattern. This optimization addresses
the memory bloat and yields a $(1.15\pm 0.03)\times$ speedup.

In Listing 2, the memory bloat occurs at line 3, which repeatedly allocates
the object collector $15179$ times. This object is passed as an input
parameter to the method search and used in many places in that method. One can
also apply the singleton pattern by hoisting the allocation site outside of
the loop enclosing the method, and declaring it as a static object. While this
optimization addresses the memory bloat, it does not bring any noticeable
speedup.

⬇

1private void makeRoom(int numValues) {

2 ...

3 if ( newSize > values.length) {

4 ...

5$\blacktriangleright$ float [] nvals = new float[nlen];

6 System.arraycopy(values, 0, nvals, 0, numVals);

7 ... }

8 ... }

Listing 1: The code snippet from Dacapo 9.12 batik. Optimizing memory bloat by
moving the object allocation site at line 5 outside of the loop yields a
nontrivial speedup ($(1.15\pm 0.03)\times$) to the entire program.

⬇

1public TopDocs search(Weight weight, Filter filter, final int nDocs) {

2 ...

3$\blacktriangleright$TopDocCollector collector = new TopDocCollector(nDocs);

4 search(weight, filter, collector);

5 ... }

Listing 2: The code snippet from Dacapo 9.12 lusearch. Optimizing memory bloat
by moving the object allocation site at line 3 outside of the loop does not
bring any speedup to the entire program.

The study of these two example code snippets reveals that basing the
optimization only on allocation frequency (or the metrics derived from the
allocation frequency (Reusable)) does not necessarily yield performance
benefits. This motivates the need for the extra locality metrics associated
with the object allocation site, which we call as object-centric profiling. To
be concrete, DJXPerf measures L1 cache misses111we can measure myriad other
events, for example, L3 cache misses, TLB misses, etc. with PMU on individual
memory access instances and aggregates the measurement of memory accesses to
the object’s allocation site. For example, DJXPerf reports that accessing the
nvals array object shown in Listing 1 accounts for 21% of total cache misses,
while accessing the collector objects in Listing 2 accounts for less than 1%
of total cache misses only, which explains the different speedups obtained
from the locality optimization. The strength of DJXPerf is its ability to
aggregate myriad accesses to the same object, scattered all over the program,
back to the same object. We emphasize that object-centric analysis does not do
away with code-centric aspect; underneath each object allocation site
$\mathcal{C}$, DJXPerf provides the ability to disaggregate the code contexts
contributing towards $\mathcal{C}$’s overall locality loss. Thus, object-
centric analysis with the locality metrics associated with the object
allocation sites is desired to determine whether locality optimization can
yield significant speedups.

###  1.2. Paper Contributions

In this paper, we propose DJXPerf, an object-centric profiler that guides data
locality optimization in Java programs. DJXPerf makes the following
contributions.

  * •

DJXPerf develops a novel object-centric profiling technique. It provides rich
information to guide locality optimization in Java programs, which yields
nontrivial speedups.

  * •

DJXPerf combines hardware performance monitoring units with minimal Java byte
code instrumentation, which typically incurs 8% runtime and 5% memory
overhead.

  * •

DJXPerf applies to unmodified Java (and languages based on JVM, e.g., Scala)
applications, the off-the-shelf Java virtual machine and Linux operating
system, running on commodity CPU processors, which can be directly deployed in
the production environment.

  * •

DJXPerf provides intuitive optimization guidance for developers. We evaluate
DJXPerf with popular Java benchmarks (Dacapo (dacapo), NPB (npb), Grande
(grande), SPECjvm2008 (specjvm2008), and the most recent Renaissance
(Prokopec:2019:RBS:3314221.3314637)) and more than 20 real-world applications.
Guided by DJXPerf, we are able to obtain significant speedups by improving
data locality in various Java programs.

###  1.3. Paper Organization

The paper is organized as follows. Section 2 describes the related work and
distinguishes DJXPerf. Section 3 introduces some background knowledge. Section
4 depicts DJXPerf’s methodology. Section 5 describes the implementation
details of DJXPerf. Section 6 evaluates DJXPerf’s accuracy and overhead.
Section 7 shows some case studies. Finally, Section LABEL:conclusion presents
some conclusions.

##  2\. Related Work

There are numerous Java performance tools assisting developers in
understanding their program behaviors, such as profiling for execution
hotspots (perf; Levon:OProfile; jprofiler-WWW; yourkit-WWW; visualvm-WWW;
async-profiler-WWW; instruction-tracing) in CPU cycles or heap usage, and
pinpointing redundant computation (toddler; ldoctor;
Dhok:2016:DTG:2950290.2950360; DellaToffola:2015:PPY:2814270.2814290). These
tools target orthogonal problems to DJXPerf, which particularly focuses on
data locality. Furthermore, there are many tools (ibs-cgo; ibs-ppopp; ibs-sc;
Liu:2015:STI:2807591.2807648; memprof; memphis; DBLP:conf/sc/BuckH04;
Roy:2016:SIF:2907294.2907308; Roy:2018:LDC:3179541.3168819) pinpointing poor
locality issues in native code via OS timers or PMU-based sampling techniques,
or code instrumentation. Unlike DJXPerf, these tools do not work for Java
applications. In this section, we only review Java profiling techniques that
are related to data locality and PMUs.

###  2.1. Data Locality Analysis in Java

Most existing Java profilers focus on memory bloat, which is one of the
locality issues (aka high memory footprint) in Java. Mitchell et al. (Causes)
design a mechanism to track data structures that suffer from excessive amounts
of memory. Their follow-up work (Sense; Fourtrends) summarizes memory usage to
uncover the costs of design decisions, which provides more intuitive guidance
for code improvement.

Xu et al. (Flow) develop copy profiling that detects data copies and suggests
removal of allocation and propagation of useless objects. Their follow-up work
(Containers) presents a technique that combines static and dynamic analyses to
identify underutilized and overpopulated containers. They also develop a
dynamic technique (Reusable) to highlight data structures that can be reused
to avoid frequent object allocations.

Nguyen and Xu (Cachetor) develop Cachetor, a value profiler for Java. Cachetor
identifies operations that keep generating identical data values and suggests
memoizing the invariant values for the future usage. Yan et al. (uncovering)
track object propagation by monitoring object allocation, copy, and reference
operations; by constructing a propagation graph, one can identify never-used
or rarely-used object allocations. Dufour et al. (Scalable; Blended) analyze
the use and shape of temporary data structures based on a blended escape
analysis to find excessive memory usage. JOLT (LJOLT) uses dynamic analysis to
identify object churn and performs function inlining.

There are few studies in measuring traditional data locality in Java programs.
Gu et al. develop ViRDA (specjvm2008-locality), which is perhaps the most
related to DJXPerf. They collect memory access trace and compute reuse
distance to quantify the temporal and spatial data locality in Java programs.

While these existing efforts can effectively identify some locality issues in
Java, they mostly suffer from two limitations. First, they employ fine-grained
byte code instrumentation, which incurs high overhead. For example, the work
(Flow; Cachetor) can incur 30-200$\times$ runtime overhead. Second, they do
not collect performance data from the real execution provided by the hardware;
instead, they employ cache simulators. Without the information of the
underlying hardware, optimization efforts may be misguided as shown in Section
1.1.

DJXPerf addresses these limitations by introducing object-centric profiling
technique, which is based on lightweight data collection from hardware PMUs.
DJXPerf is not a replacement for existing tools; it provides complementary
information to save non-fruitful optimization efforts.

###  2.2. Java Profilers Based on PMUs

Sweeney et al. (pmu-java-behavior) develop a system to help interpret results
obtained from PMUs when analyzing a Java application’s behavior. Cuthbertson
et al. (pmu-runtime-components) map the instruction IP address based hardware
event information to the JIT server components. Goldshtein (profiling-JVM-
production) monitors CPU bottlenecks, system I/O load and GC with perf in
production JVM environments. Hauswirth et al. (Vertical) introduce vertical
profiling, adding software performance monitors (SPMs) to observe the behavior
in the layers (VM, OS, and libraries) above the hardware. Georges et al.
(Phase) measure the execution time for each method invocation with PMUs and
study method-level phase behaviors in Java applications. Lau et al. (auditing)
guide inline decisions in a dynamic compiler with the direct measure of CPU
cycles. Eizenberg et al. (remix) utilize PMUs to identify false sharing in
Java programs.

Unlike these existing approaches, DJXPerf leverages PMUs to identify data
locality in Java programs. Its usage of lightweight PMU measurement for
object-centric analysis is unique among all existing Java profilers.

###  2.3. NUMA Analysis in Java

Gidra et al. (hal-00868012) study the scalability of throughput-oriented GCs
and propose to map pages and balance GC threads across NUMA nodes. Gidra et
al. (NumaGiC) propose local mode for NUMA machines to forbid GC threads to
steal references from remote NUMA nodes so as to avoid costly cross-node
memory accesses. Maria et al. (GCNUMA) show how to optimize three main GCs in
OpenJDK, i.e., ParallelOld, ConcurrentMarkSweep, and G1 in multicore NUMA
machines. Tikir et al. (JavaHeaps) propose NUMA-aware heap configurations for
Java server applications to improve the memory performance during the GC
phase. Raghavendra et al. (CCNUMA) propose a dynamic compiler scheme for
splitting the Java code buffer on a CC-NUMA machine.

While these works can identify some memory access latency issues, they cannot
pinpoint the object-level remote memory access issue. DJXPerf is able to
identify NUMA locality and does not depend on the GC.

##  3\. Background

DJXPerf leverages facilities available in commodity Java virtual machines
(JVM) and CPU processors, which we introduce in this section.

#### ASM Framework

ASM (asm) is a Java byte code manipulation and analysis framework. ASM can
modify existing classes or dynamically generate classes, supporting custom
complex transformations and code analysis tools. ASM focuses on performance,
with an emphasis on the low overhead, which makes it suitable for dynamic
analysis. ASM can instrument object allocation (e.g., new) and capture the
object information, such as allocation size and context.

#### Java Virtual Machine Tool Interface (JVMTI)

JVMTI (JVMTI) is a native programming interface of the JVM, which supports
developing debuggers/profilers (aka JVMTI agents) in C/C++ based native
languages to inspect JVM internals. JVMTI provides a number of event callbacks
to capture JVM start and end, thread creation and destruction, method loading
and unloading, garbage collection epochs, to name a few. User-defined
functions are subscribed to these callbacks and invoked when the associated
events happen. Also, JVMTI maintains a variety of JVM internal states, such as
the map from the machine code of each JITted method to byte code and source
code, and the call path for any given point during the execution. Tools based
on JVMTI can query these states at any time. JVMTI is available in off-the-
shelf Oracle HotSpot JVM (hotspot-jvm).

#### Hardware Performance Monitoring Unit (PMU)

Modern CPUs expose programmable registers (aka PMU) that count various
hardware events such as memory loads, stores, and CPU cycles. These registers
can be configured in sampling mode: when a threshold number of hardware events
elapse, PMUs trigger an overflow interrupt. A profiler can capture the
interrupt as taking a sample and attribute the metrics collected along with
the sample to the execution context. PMUs are per CPU core and virtualized by
the operating system (OS) for each thread.

Intel offers Precise Event-Based Sampling (PEBS) (IntelArch:PEBS:Sept09) in
SandyBridge and following generations. PEBS provides the effective address
(EA) at the time of the sample when the sample is for a memory load or store
instruction. PEBS also reports memory-related metrics of the sampled
loads/stores such as cache misses, TLB misses, memory access latency. This
facility is often referred to as address sampling — a building block of
DJXPerf. AMD Instruction-Based Sampling (AMDIBS:07) and PowerPC Marked Events
(Srinivas:2011:IBMJ-Power7) offer similar capabilities.

#### Linux perf_event.

Linux offers a standard interface to program and sample PMUs via the
perf_event_open system call (perfevents) as well as the associated ioctl
calls. The Linux kernel can deliver a signal to the specific thread whose PMU
event overflows. The user code can extract PMU performance data and execution
contexts at the signal handler.

##  4\. Methodology

Figure 2 overviews DJXPerf’s object-centric profiling. DJXPerf includes two
agents: a Java agent and a JVMTI agent. The Java agent adds lightweight byte
code instrumentation to capture object allocation information during
execution, such as the allocation context and address range of objects. The
JVMTI agent subscribes to Java thread creation callbacks to enable PMU to
sample memory accesses. When PMU interrupts a thread with a sampled address,
DJXPerf associates the address seen in the sample with the Java object
enclosing that address, as shown in Figure 2. In the rest of this section, we
elaborate on each agent and discuss their interactions for the object-centric
analysis.

Figure 2. Overview of DJXPerf’s object-centric analysis.

###  4.1. Java and JVMTI Agents

#### Capturing Object Addresses via A Java Agent

DJXPerf leverages a Java agent to capture object allocation. The Java agent is
based on the ASM framework (asm). The Java agent scans Java byte code and
instruments four object allocation routines — new, newarray, anewarray, and
multianewarray. The Java agent inserts pre- and post-allocation hooks to
intercept each object allocation and returns the object information (e.g.,
object pointer, type, and size) via user-defined callbacks. Upon each
allocation callback, we follow an existing technique (object-addr) to obtain
the memory range allocated for each Java object.

#### Generating Memory Access Samples via JVMTI Agent

DJXPerf leverages a JVMTI agent to sample and collect memory accesses. With
the help of JVMTI, DJXPerf can intercept Java thread start, where DJXPerf
configures PMUs to sample precise events for cache misses (e.g.,
MEM_LOAD_UOPS_RETIRED:L1_MISS), TLB misses (e.g., DTLB_LOAD_MISSES), or memory
access latency (e.g., MEM_TRANS_RETIRED:LOAD_LATENCY). DJXPerf also installs a
signal handler to process PMU samples. On thread termination, DJXPerf stops
PMUs and produces a profile for each thread. Besides controlling PMUs, DJXPerf
also utilizes the JVMTI agent to capture the calling contexts for both PMU
samples and object allocations, which is described in Section 4.4.

###  4.2. Object-centric Attribution

#### Identifying Objects

Java objects are allocated on the heap. How to represent an object to a
developer is a challenging question. We adopt a simple and perhaps most
intuitive approach that developers can identify with the allocation call path
leading to the object allocation. We represent a call path where an object $O$
was allocated with ${\mathcal{P}}(O)$. An application may create multiple
objects via a single allocation site, for example, in a loop. In our approach,
all such objects will be represented by a single call path and become
indistinguishable from one another; we accept this trade-off since objects
allocated at the same call path are likely to exhibit similar behavior.
DJXPerf’s Java agent captures each allocation instance and invokes the JVMTI
agent to obtain the allocation call path. As these allocation instances share
the same call path, DJXPerf associates the PMU metrics for any of those
objects with the same call path.

#### Attributing PMU Samples to Objects

DJXPerf utilizes an efficient interval splay tree (splay-tree) to maintain the
memory ranges allocated for all the monitored objects. On each PMU sample,
DJXPerf uses the effective address $M$ presented by the PMU to look up into
the splay tree. The lookup for $M$ returns the object $O$ whose memory range
encloses the sampled address. DJXPerf then attributes any associated PMU
metric related with the sample to ${\mathcal{P}}(O)$ — the object’s allocation
call path.

###  4.3. Object NUMA locality detection

On each PMU sample, DJXPerf uses the effective address $M$ to identify a
memory page in libnuma library function numa_move_pages, which simply uses the
move_pages system call. Not only can move_pages move a specified page to a
specified NUMA node, but also return the NUMA node where the page is currently
residing. Then DJXPerf is able to identify which NUMA node ($Node_{1}$) the
current object is allocated. Still on each PMU sample, DJXPerf uses
PERF_SAMPLE_CPU identifier, which contains the CPU number, to show which NUMA
node ($Node_{2}$) the current object is accessing. If $Node_{1}$ and
$Node_{2}$ are distinct nodes, then DJXPerf reports a remote memory access for
this object.

###  4.4. Calling Context Determination

We associate an object allocation with the full calling context (aka call
path) leading to its allocation. The full call path helps distinguish
allocations by the same routine called from different code contexts. The
alternative, a flat profile, would be unable to distinguish, for example, an
allocation in a common library routine called from two different user code
locations.

Oracle Hotspot JVM supports two JVMTI APIs to obtain calling contexts:
GetStackTrace and AsyncGetCallTrace. GetStackTrace requires the program to
reach a safe point to collect calling context, which produces biased results
(Mytkowicz:2010:EAJ:1806596.1806618; Hofer:2014:FJP:2647508.2647509). Instead,
DJXPerf employs AsyncGetCallTrace to obtain calling contexts at anytime
(AsyncGetCallTrace-WWW). AsyncGetCallTrace accepts u_context obtained at PMU
interrupts or object allocations, and returns the byte code index (BCI) and
method ID for each frame in the calling context. Usually, a single Java source
line may translate to several byte code instructions, and the BCI can tell
which byte code instruction was executed. Since an individual method may be
JITted multiple times, the method ID helps distinguish different JITted
instances of the same method. With the method ID, DJXPerf obtains the
corresponding class name and method name by querying JVM. To obtain the line
number, DJXPerf maintains a “BCI$\rightarrow$line number” map for each method
instance via JVMTI API GetLineNumberTable and queries the line number on
demand.

###  4.5. Interfering with Garbage Collection

The garbage collector (GC) complicates object-centric attribution because GC
implicitly reclaims memory of unused objects and moves objects for compact
memory layouts. The trigger of the GC thread is determined by JVM, which is
transparent to Java applications. Ignoring GC, DJXPerf may yield incorrect
object attribution. We assume GC reclaims or moves an object
$\mathcal{O}_{1}$, whose memory can be reused by another allocation, say
object $\mathcal{O}_{2}$. In this case, a tool may incorrectly attribute PMU
samples that touch $\mathcal{O}_{2}$ to $\mathcal{O}_{1}$. Moreover, if
$\mathcal{O}_{1}$ is moved to a new memory location, any subsequent PMU
samples of the new address will be unavailable for us to map via the original
mapping maintained in the splay tree.

Handling GC is necessary in DJXPerf. Unfortunately, JVM exposes limited
information about GC via JVMTI: JVMTI only provides hooks to register
callbacks on GC start and end, with no insight about the individual object
behavior (i.e., reclamation and movement). We offer a solution to handle all
kinds of GC in the off-the-shelf JVM.

#### Solution for Object Movement by GC

Our solution is based on an important observation from the source code of
OpenJDK: GC moves objects using the memmove function. Thus, DJXPerf overloads
memmove to obtain the source and destination of every moved object and update
the memory ranges associated with this object in the splay tree described in
Section 4.2. However, updating the splay tree upon each memmove invocation is
costly. Instead, DJXPerf creates a relocation map for each thread to record
the moved objects (e.g., source as the key, destination memory addresses, and
size as the value). DJXPerf updates the objects in the map in a batch at the
end of each GC invocation.

To capture every GC invocation, DJXPerf utilizes JVM management interface,
i.e., MXBean. DJXPerf, in the Java agent, registers GC invocation callbacks
via GARBAGE_COLLECTION_NOTIFICATION event. Upon each GC completion, an MXBean
instance (i.e., GarbageCollectorMXBean) emits a callback; DJXPerf captures
this callback and updates all the newly moved objects in the relocation map to
the splay tree. The relocation map is reset after the update.

It is worth noting that DJXPerf may not always capture all the object
allocation because its attach mode may omit some allocations (see Section
5.1). If this is the case, DJXPerf directly inserts the new memory intervals
for the moved objects.

#### Solution for Object Reclamation by GC

DJXPerf handles object reclamation by overloading the finalize method. GC
always calls the finalize method before reclaiming memory for any object,
which cleans up resources allocated to the object. DJXPerf intercepts the
finalize method, obtains the memory interval reclaimed, and removes it from
the splay tree.

##  5\. Implementation

DJXPerf is a user-space tool with no need for any privileged system
permissions. DJXPerf requires no modification to hardware, OS, JVM, or
monitored applications, which makes DJXPerf applicable to the production
environment. Figure 3 shows the workflow of DJXPerf, which consists of an
online data collector and an offline data analyzer. There are two ways to
enable the collector. If we need to profile Java source code as soon as the
JVM starts up, we can launch DJXPerf as an agent by passing JVM options. If
the JVM is already started, we can attach DJXPerf to this running JVM. The
collector gleans the measurement via the Java and JVMTI agents and generates a
profile file per thread. The analyzer then aggregates the files from different
threads, sorts the metrics, and highlights the problematic objects for
investigation.

The implementation challenges include maintaining a low measurement overhead
and scaling the analysis to many threads. In the rest of this section, we
discuss how DJXPerf addresses these challenges.

Figure 3. The workflow of DJXPerf.

###  5.1. Online Collector

DJXPerf supports two modes to monitor a Java program. On the one hand, DJXPerf
can monitor the end-to-end execution of a program by launching the tool
together with the program. On the other hand, DJXPerf can attach and detach to
any running Java program to collect the object-centric profile for a while.
This is particularly useful to monitor long-running programs such as web
servers or microservices.

DJXPerf accepts any memory-related PMU precise events. In our implementation,
DJXPerf presets the event as L1 cache misses (MEM_LOAD_UOPS_RETIRED:L1_MISS).
We empirically choose a sampling period to ensure DJXPerf is able to collect
20-200 samples per second per thread, which has a good trade-off between
runtime overhead and statistical accuracy (Tallent:2010:phd).

To minimize the thread synchronization, DJXPerf has each thread collect PMU
samples independently and maintains the calling contexts of PMU samples in a
compact calling context tree (CCT) (Arnold-Sweeney:1999:cct), which merges all
the common prefixes of given calling contexts. The only shared data structure
between threads is the splay tree for objects because an object allocated by a
thread can be accessed by other threads. DJXPerf uses a spin lock to ensure
the integrity of the splay tree across threads.

Another source of overhead is monitoring objects, which depends on a given
Java application. DJXPerf can either monitor every object allocation, or
filter out objects whose sizes are smaller than a configurable value
$\mathcal{S}$ from monitoring to trade off the overhead. DJXPerf by default
sets $\mathcal{S}$ as 1KB to pinpoint large objects that are more vulnerable
to locality issues. We evaluate the impact of $\mathcal{S}$ in Section 6.

(a) Runtime overheads.

(b) Memory overheads.

Figure 4. DJXPerf’s runtime and memory overheads in the unit of times
($\times$) on various benchmarks.

###  5.2. Offline Analyzer

To generate compact profiles, which is important for scalability, DJXPerf’s
offline analyzer merges profiles from different threads. Object-centric
profiles, organized as a CCT per thread, are amenable to coalescing. The
analyzer merges CCTs in a top-down way — from call path root to leaf. Call
paths for individual objects and their memory accesses can be merged
recursively across threads. If object allocation call paths are the same, they
have coalesced even if they are from different threads. All memory accesses
with their call paths to the same objects are merged as well. Metrics are also
summed up when merging CCT nodes. Typically, DJXPerf’s analyzer requires less
than one minute to merge all profiles in our experiments. DJXPerf provides a
Python-based GUI to visualize the profiles for intuitive analysis.

###  5.3. Discussions

DJXPerf is a sampling-based dynamic profiling tool. The sampling strategy only
identifies statistically significant performance issues and ignores some
insignificant ones. Also, the sampling rate should be appropriately chosen. A
high sampling rate brings high overhead, and a low sampling rate obtains
insufficient samples, which can result in over- or under-estimation.
Nevertheless, there is sufficient evidence to show that random sampling via
PMUs is superior to biased sampling (Mytkowicz:2010:EAJ:1806596.1806618). Like
other dynamic profilers DJXPerf’s optimization guidance is input dependent. We
recommend to use typical program inputs for representative profiles.
Additionally, we ensure the optimization is correct across different inputs.
Finally, DJXPerf pinpoints objects potentially for optimization, but users
need to determine and apply the optimization.

##  6\. Evaluation

We evaluate DJXPerf on a 24-core Intel Xeon E5-2650 v4 (Broadwell) CPU clocked
at with 2.2GHz running Linux $4.18$. The memory hierarchy consists of a
private 32KB L1 cache, a private 256KB L2 cache, a shared 30MB L3 cache, and
256GB main memory. DJXPerf works for any Oracle JDK version with the JVMTI
support; in this experiment, we run all applications in Oracle Hotspot JVM
with JDK 1.8.0_161.

#### Accuracy Analysis

We show that DJXPerf can accurately pinpoint Java objects with the poor
locality. We evaluate DJXPerf’s ability to find performance bugs on five
benchmarks that have locality issues reported by prior work (Reusable). These
five benchmarks are luindex, bloat, lusearch, and xalan, all from Dacapo 2006
(dacapo), as well as SPECJbb2000 (specjbb2000). DJXPerf successfully
identified all the locality issues as reported by existing tools (Reusable).
We elaborate the analysis of these benchmarks in the appendix since they have
already been discussed elsewhere.

#### Overhead Analysis

The runtime overhead (memory overhead) is the ratio of the runtime (peak
memory usage) under monitoring with DJXPerf to the runtime (peak memory usage)
of the corresponding native execution. To quantify the overhead of DJXPerf in
both runtime and memory, we apply DJXPerf to a number of well-known Java
benchmark suites, such as the most recent JVM parallel benchmarks suite
Renaissance (Prokopec:2019:RBS:3314221.3314637), Dacapo 9.12 (dacapo-9.12),
and SPECjvm2008 (specjvm2008). We run all benchmarks with four threads if
applicable. We run every benchmark 30 times and compute the average and error
bar. Figure 4 shows the overhead when DJXPerf is enabled at a sampling period
of 5M for Renaissance benchmark suite (Prokopec:2019:RBS:3314221.3314637),
Dacapo 9.12 (dacapo-9.12), and SPECjvm2008 (specjvm2008). Some Renaissance and
Dacapo benchmarks have higher time overhead (larger than 30%) because they
usually invoke too many allocation site callbacks (e.g., more than $400$
million times for mnemonics, par-mnemonics, scrabble, akka-uct, db-shootout,
dec-tree, and neo4j-analytics). From Figure 4 we can see that DJXPerf
typically incurs 8% runtime and 5% memory overhead.

#### Further Discussions

To trade off the overhead, DJXPerf allows users to set up a configurable value
$\mathcal{S}$ to capture memory allocations with the size greater than
$\mathcal{S}$. We also test an extreme case: setting $\mathcal{S}$ to 0, which
means DJXPerf captures the allocation for each object. With the evaluation on
the Renaissance benchmark suite (Prokopec:2019:RBS:3314221.3314637), DJXPerf
incurs a runtime overhead ranging from $1.8\times$ to $3.6\times$ to monitor
every object allocation. With further investigation, we seldom find
opportunities for optimizing small-sized objects. Thus, we believe setting
$\mathcal{S}$ to 1KB is a good trade-off between the overhead and obtained
insights. One can expect DJXPerf to be used in attach and detach mode on
production services, where developers collect profiles from multiple instances
of their services; hence, the overhead, if any, is introduced only for the
short duration of measurement and the samples from multiple instances will
offer a good coverage.

Table 1. Overview of performance optimization guided by DJXPerf.

##  7\. Case Studies

DJXPerf’s low overhead allows us to collect object-centric profiles from a
variety of Java and Scala applications, such as the Renaissance benchmark
suite (Prokopec:2019:RBS:3314221.3314637), ObjectLayout (ObjectLayout),
Findbugs (FindBugs), Ranklib (Ranklib), cache2k (cache2k), Apache SAMOA
(SAMOA), Apache Commons Collections (Commons), Java Grande 2.0 (grande), to
name a few. We run these applications with the default inputs released with
these applications or the inputs that we can find to our best knowledge. To
fully utilize CPU resources, we run each parallel application to saturate all
CPU cores if not specified. DJXPerf can pinpoint many previously not reported
data locality issues and guide optimization choices. To guarantee correctness,
we ensure the optimized code passes the application validation tests. To avoid
system noises, we run each application 30 times and use a 95% confidence
interval for the geometric mean speedup to report the performance improvement,
according to the prior approach (inefficiencies-in-java). Table 1 overviews
the performance improvements on several real-world Java applications guided by
DJXPerf. In the remaining section, we elaborate on the analysis and
optimization of several applications under the guidance of DJXPerf in Section
7.1\- LABEL:case2. Due to the page limit, we omit the description of other
applications in Table 1. Section LABEL:adversary shows some studies on
optimizing insignificant objects, which illustrate the unique usefulness of
DJXPerf over other tools.

We also collected code-centric profiles using the Linux perf utility for each
case study to compare with DJXPerf’s profiles. In several cases, we found it
arduous to tie data accesses segregated over many code location back to the
object allocation site in code-centric profiles. DJXPerf eased developer’s
task by showing top data objects subject to locality problems along with an
ordered, hierarchical view of code locations contributing to the locality
problem.

To optimize the NUMA locality issue, we developed a Java library to access the
libnuma library interfaces. As the libnuma library can be used only in native
languages, we leverage Java Native Interface (JNI) to enable our Java library
to access the native NUMA API. After DJXPerf detected the problematic object
that suffers from remote memory access, we modify the Java application
allocation code for this object by calling the libnuma numa_alloc_interleaved
API. Then, we can allocate this problematic object interleaved on all NUMA
nodes to reduce the remote accesses.

###  7.1. ObjectLayout 1.0.5

ObjectLayout (ObjectLayout) is a layout-optimized Java data structure package,
which provides efficient data structure implementation. We run ObjectLayout
with the SAHashMap input released with the package. DJXPerf reports four
problematic objects, which account for 84% of cache misses in the entire
program. Figure 5 shows the snapshot of DJXPerf’s GUI for intuitive analysis.
The top pane of the GUI shows the Java source code; the bottom left pane shows
the object allocation (in red) and accesses (in blue) in their full call
paths; and the bottom right pane shows the metrics (e.g., L1 cache misses,
object allocation times in this example).

The GUI in Figure 5 shows one problematic object, which is at line 292 of
method allocateInternalStorage in class AbstractStructuredArrayBase. The
allocateInternalStorage method is repeatedly invoked in a loop when a new
instance is created by the newInstance method. The bottom left pane of the GUI
shows one problematic object allocation in the full call path, which is
allocated 217 times in a loop. There are multiple sampled accesses associated
with this allocation site and they account for 30.4% L1 cache misses of the
entire program. To save the space, we only show one access in its call path in
blue (method getNode in class SAHashMap) that accounts for most of the cache
misses. For the other accesses, we only show their call paths rooted at
java.lang.Thread.run; with no object-centric profiling, these accesses are
separately presented with no aggregate view.

We further investigate the source code and find that the problematic object is
array intAddressableElements. The life cycles of different instances do not
overlap, which means using singleton pattern of this object (i.e., allocating
a single object instance and reusing it without creating more instances) is
safe and avoids memory bloat. To apply the singleton pattern, we hoist
intAddressableElements allocation out of allocateInternalStorage method, which
is thread safe. We optimize three other problematic objects with similar
methods. Our optimization reduces total cache misses by 76% and yield a
$(1.45\pm 0.07)\times$ increase in throughput.

Figure 5. The top-down object-centric GUI view of ObjectLayout shows a
problematic object’s allocation site in source code, and its allocation call
path with its all access call paths.

###  7.2. FindBugs 3.0.1

FindBugs is a program to find bugs in Java programs. It looks for instances of
“bug pattern” — code instances that are likely to be errors (FindBugs). We run
FindBugs on Java chart library 1.0.19 version as input. DJXPerf reports two
objects that account for 32% of cache misses in the entire program as shown in
Listings 3 and 4. The two problematic objects buf and IdentityHashMap are both
repeatedly allocated in loops with no overlap in lifecycles across different
instances. We apply singleton pattern by hoisting the two object allocations
out of the loops to avoid memory bloat. These optimizations reduce peak memory
usage from 1.8GB to 0.9GB, yielding a $(1.11\pm 0.01)\times$ speedup to the
entire program.

⬇

634public void setAppClassList(List<ClassDescriptor> appClassCollection) {

635 for (ClassDescriptor appClass : allClassDescriptors) {

636 ...

637 $\blacktriangleright$XClass xclass =
currentXFactory().getXClass(appClass);

638 //getXClass method will call to parse method below

639 }}

640public void parse(ClassInfo.Builder builder) {

641 ...

642 $\blacktriangleright$char[] buf = new char[1024];

643 ...}

Listing 3: The problematic source code highlighted by DJXPerf in FindBugs.

⬇

111private void analyzeApplication() throws InterruptedException {

112 for (Detector2 detector : detectorList) {

113 ...

114 $\blacktriangleright$detector.visitClass(classDescriptor);

115 //visitClass method will call to analyzeMethod method below

116 }}

117private void analyzeMethod(ClassContext classContext, Method method) {

118 ...

119 $\blacktriangleright$IdentityHashMap<InstructionHandle, Object>
sometimesGood = new IdentityHashMap<InstructionHandle, Object>();

120 ... }

Listing 4: The source code highlighted by DJXPerf shows the problematic object
sometimesGood (allocated at line 120) suffering from poor locality.

###  7.3. Renaissance 0.10: scala-stm-bench7

scala-stm-bench7 is a Renaissance (Prokopec:2019:RBS:3314221.3314637)
benchmark, which runs stmbench7 code using ScalaSTM (scalastm) for
parallelism. It is written in Scala. We run scala-stm-bench7 using the default
60 repetitions. DJXPerf pinpoints a problematic object _wDispatch as shown in
Listing 5. This object accounts for 25% of total cache misses. With further
investigation, we find that the method grow is called frequently to adjust the
_wDispatch array capacity and create a new _wDispatch array. Such frequent
invocation of grow is because the initial size of _wDispatch array is only 8.
For optimization, we increase the initial size of _wDispatch array to be 512,
which reduces array creation and copy by 79%. This optimization yields a
$(1.12\pm 0.04)\times$ speedup to the entire program.

⬇

615private def grow() {

616 _wCapacity *= 2

617 if (_wCapacity > _wDispatch.length) {

618 ...

619 $\blacktriangleright$_wDispatch = new Array[Int](_wCapacity)

620 } ... }

Listing 5: DJXPerf pinpoints _wDispatch object suffering from high cache
misses in scala-stm-bench7.  Table 2. Optimizing insignificant objects yields
little speedups.

###  7.4. SPECjvm2008: Scimark.fft.large

Scimark (scimark) is a composite Java benchmark measuring the performance of
numerical codes occurring in scientific applications. Scimark.fft refers to a
fast Fourier transform (FFT) implementation. We run Scimark.fft with its large
input released with the benchmark. DJXPerf reports the object data, which is
an array, suffering most from cache miss (accounting for 75.5% of total cache
misses). The most problematic accesses are at lines 171, 172, 174, and 175 in
method transform_internal of class FFT, as shown in Listing 6. From the code
listing we can see that array data is accessed in a 3-level loop nest. The
innermost loop index b increases by $2*dual$ every iteration, and $dual$ is
also doubled every iteration of the outer-most loop. Thus, the accessing
stride for data array is large, resulting in the poor spatial locality. For
optimization, we interchange loops a and b to reduce the stride. This
optimization reduces cache misses of the entire program by 70%, yielding a
$(2.37\pm 0.07)\times$ speedup.

⬇

165protected void transform_internal (double data[], int direction) {

166 for (int bit = 0, dual = 1; bit < logn; bit++, dual *= 2) {

167 for (int a = 1; a < dual; a++) {

168 for (int b = 0; b < n; b += 2 * dual) {

169 int i = 2*(b + a);

170 int j = 2*(b + a + dual);

171 $\blacktriangleright$double z1_real = data[j];

172 $\blacktriangleright$double z1_imag = data[j+1];

173 ...

174 $\blacktriangleright$data[j] = data[i] - wd_real;

175 $\blacktriangleright$data[j+1] = data[i+1] - wd_imag;

176 ...

177}}}}

Listing 6: DJXPerf identifies the data array with poor locality in
SPECjvm2008: Scimark.fft.large.

###  7.5. Eclipse Collections

Eclipse Collections is a comprehensive Java collections library, which enables
productivity and performance by delivering an expressive and efficient set of
APIs and types (Eclipse). We run eclipse collections using CollectTest as
input. After profiling eclipse collections, DJXPerf reports an object that
suffers from NUMA remote accesses, the Integer array result, which is
allocated at line 758 in method toArray of class Interval and accessed at line
245 in method batchFastListCollect of class InternalArrayIterate with a high
percentage of NUMA remote accesses (73.4%). By investigating the source code
as shown in Listing LABEL:eclipse_collections_listing, the program first calls
to toArray method to allocate and initialize an Integer array result. And
then, the program passes the result to batchFastListCollect method and
accesses it at line 245. DJXPerf detects that there’s a mismatch between the
allocation of result and initialization by the master thread in one NUMA
domain, and accesses by the worker threads executing in other NUMA domains.
The workers all compete for memory bandwidth to access the data in the
master’s NUMA domain. To avoid contending for data allocated in a single NUMA
domain, we optimized the program as allocating and initializing the object
result in every NUMA domain. The optimization reduces remote accesses by 41%
and increases the throughput (operations per second) by $(1.13\pm
0.04)\times$.

⬇

235//Interval.java

236public Integer[] toArray() {

237 $\blacktriangleright$Integer[] result = new Integer[this.size()];

238 ...

239 return result;

240}

241//InternalArrayIterate.java

242private static <T> void batchFastListCollect(T[] array, ...) {

243 ...

244 for (int i = start; i < end; i++)

245 $\blacktriangleright$castProcedure.value(array[i]);

246 ...

247}

⬇

1\end{figure}

2

3

4\subsection{Apache Druid}

5\label{case2}

6Apache Druid is a high performance real-time analytics database designed for
workflows where fast queries and ingest matter~\cite{Druid}. We run Apache
Druid using BitmapIterationBenchmark as input. After profiling SP, \tool{}
reports an array an BitSet object, {\tt bitmap}, which is initialized at line
37 in constructor method {\tt WrappedImmutableBitSetBitmap} of class {\tt
WrappedImmutableBitSetBitmap} and accessed at line 120 in method {\tt next} of
same class. Listing~\ref{druid listing} shows the problematic object is the
{\tt bitmap} (accessed at line 120), which more than half of total memory
accesses are remote accesses. With further investigation, we find that the
problematic object {\tt bitmap} is initialized in constructor method {\tt
WrappedImmutableBitSetBitmap} executed in one NUMA domain, but accessed by
many threads in other NUMA domains. To address this problem, we parallelize
the allocation and initialization for this object {\tt bitmap} to ensure that
each thread first touches its own data. With this optimization, we reduce
remote accesses by 47\% and increases the throughput by $(1.75\pm0.05)\times$.

7

8\begin{figure}

9\begin{lstlisting}[firstnumber=112,language=java]

10public class WrappedImmutableBitSetBitmap {

11 protected final BitSet bitmap;

12 public WrappedImmutableBitSetBitmap(BitSet bitmap) {

13 $\blacktriangleright$this.bitmap = bitmap;

14 }

15 ...

16 public int next() {

17 int pos = nextPos;

18 $\blacktriangleright$nextPos = bitmap.nextSetBit(pos + 1);

19 return pos;

20 }

21}

⬇

1\end{figure}

2

3

4\subsection{Attempts to Optimization for Insignificant Objects}

5\label{adversary}

6%{\color{red}Could you revisit Harry’s paper to see what metrics they use to
identify memory bloat? Do they just use the allocation times?}

7To demonstrate the importance of PMU metrics (i.e., cache misses in our
experiments) associated with the objects, we show a number of studies on
attempting to optimize insignificant objects in

8Table~\ref{adversary study table}.

9All these code bases have the memory bloat problem: repeatedly allocate
objects many times, and different instances have no overlap in their life
intervals.

10In the table, we show the location of problematic object allocations, the
number of object instances, the associated cache miss metrics, and the
speedups after optimization.

11Our studies show that these optimizations yield negligible speedups, which
emphasize the fact that these objects account for very few cache misses. Thus,
\tool{}’s object-centric analysis is useful to filter out insignificant
objects for non-fruitful optimization.

12

13

14%\milind{Not sure adversary is the correct term here. Basically you are
saying that \tool{} highlights only candidates that have performance
optimization potential. This is a hard argument to sell. If cache miss is
negligible in the entire program and some object incurs 99\% cache miss, there
may be no point optimizing it. The metric has to be relative to the total
program execution time. More specifically, I can expect some reviewers to
question, whether the tool can quantify the speed-up without optimizing the
code? That is what developers want to see.}

15

16%In table \ref{adversary study table}, we listed some applications with
their problematic code locations. These problematic locations are the
allocation sites which create objects iteratively. We also listed the
allocation times for each created object. The common feature of these
problematic allocation sites is that all of these objects have very low L1
cache misses when they are accessed. After optimized these problematic code,
we saw a negligible speedup (<1\%).

17

18\begin{comment}

19

20\subsubsection{Dacapo 2006 Chart}

21Chart uses JFreeChart to plot a number of complex line graphs and renders
them as PDF. We ran it with large workload. In listing \ref{adversary chart},
our profiler reports the array cohortVolumes (line 2) suffers from memory
bloat but has very little cache miss (no more than 10 cache misses) when
accessing this array cohortVolumes (line 5 and line 10). After moving this
allocation site out of method XYSeriesCollection and making it referenced by a
static field, we saw a negligible speedup (only 0.5\%).

22

23\begin{figure}

24\begin{lstlisting}[firstnumber=1,language=java]

25public static XYSeriesCollection createHeapData(...) {

26 $\blacktriangleright$double[] cohortVolumes = new double[currCohortCount];

27 do {

28 ...

29 $\blacktriangleright$cohortVolumes[index] =
Double.parseDouble(st.nextToken(","));

30 } while(...)

31 ...

32 for(int i=0; i<currCohortCount; i++) {

33 for(int j=currCohortCount-1; j>=i; j\--) {

34 $\blacktriangleright$tempVolumes[i] += cohortVolumes[j];

35 }

36 }

37 ...

38}

⬇

1\end{figure}

2

3\subsubsection{Dacapo 2006 luindex}

4Luindex uses lucene to indexes a set of documents. We ran it with default
workload. In listing \ref{adversary luindex}, our profiler reports the array
newPositions (line 5) suffers from memory bloat. However, this allocation site
has very little cache miss (only 4 cache misses when accessing array
newPositions at line 7 and line 9). After moving this allocation site out of
method addPosition, the optimized running time is same with the original
running time.

5

6\begin{figure}

7\begin{lstlisting}[firstnumber=1,language=java]

8private final void addPosition(...) {

9 ...

10 Posting ti = (Posting) postingTable.get(termBuffer);

11 int freq = ti.freq;

12 $\blacktriangleright$int[] newPositions = new int[freq * 2];

13 for (int i = 0; i < freq; i++) {

14 $\blacktriangleright$newPositions[i] = positions[i];

15 }

16 $\blacktriangleright$ti.positions = newPositions;

17 ...

18}

⬇

1\end{figure}

2

3

4\subsubsection{Dacapo 9.12 lusearch}

5Lusearch uses lucene to do a text search of keywords over a corpus. We ran it
with large workload. In listing \ref{adversary lusearch}, our profiler reports
the TopDocCollector object collector (line 3) suffers from memory bloat. This
collector object is passed to a search method (line 7). Inside this search
method, this input parameter (results) is accessed at line 9 and line 12.
However, the accessing for object results has very little cache miss (only 12
cachesses). We created a static field to cache the instance of object
collector (line 3). This fix only led to a running time reduction by $1\%$.

6

7\begin{figure}

8\begin{lstlisting}[firstnumber=1,language=java]

9public TopDocs search(Weight weight, Filter filter, final int nDocs) {

10 ...

11 $\blacktriangleright$TopDocCollector collector = new
TopDocCollector(nDocs);

12 search(weight, filter, collector);

13 ...

14}

15public TopFieldDocs search (..., TopDocCollector results) {

16 ...

17 $\blacktriangleright$scorer.score(results);

18 while(...) {

19 ...

20 $\blacktriangleright$results.collect(scorerDocId, scorer.score());

21 }

22}

⬇

1\end{figure}

2\end{comment}

3

4\section{Conclusions}

5\label{conclusion}

6In this paper, we present \tool{}, the very first lightweight Java profiler
that performs object-centric analysis to identify data locality issues in Java
applications. \tool{} leverages the lightweight Java byte code instrumentation
and the hardware PMU available in commodity CPU processors. \tool{} works for
off-the-shelf Linux OS and Oracle Hotspot JVM, as well as unmodified Java
applications. \tool{} incurs low overhead, typically 8\% in runtime and 5\% in
memory.

7These features make \tool{} applicable to the production environment. \tool{}
is able to identify a number of locality issues in real-world Java
applications. Such locality issues arise due to traditional spatial/temporal
data locality and also due to memory bloat.

8Guided by \tool{}, we are able to perform optimization, which yields
nontrivial speedups.

9\tool{} is open-sourced at an \texttt{anonymous} URL.

10

11

12%%

13%% The next two lines define the bibliography style to be used, and

14%% the bibliography file.

15\bibliographystyle{ACM-Reference-Format}

16{\small

17\bibliography{datacentric}}

18

19%%

20%% If your work has an appendix, this is the place to put it.

21\appendix

22

23

24\end{document}

25\endinput

26%%

27%% End of file ‘sample-sigconf.tex’.’