Static Analyses for Eliminating Unnecessary Synchronization from Java Programs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999-10-01

AUTHORS

Jonathan Aldrich , Craig Chambers , Emin Gun Sirer , Susan Eggers

ABSTRACT

This paper presents and evaluates a set of analyses designed to reduce synchronization overhead in Java programs. Monitor-based synchronization in Java often causes significant overhead, accounting for 5–10% of total execution time in our benchmark applications. To reduce this overhead, programmers often try to eliminate unnecessary lock operations by hand. Such manual optimizations are tedious, error-prone, and often result in poorly structured and less reusable programs. Our approach replaces manual optimizations with static analyses that automatically find and remove unnecessary synchronization from Java programs. These analyses optimize cases where a monitor is entered multiple times by a single thread, where one monitor is nested within another, and where a monitor is accessible by only one thread. A partial implementation of our analyses eliminates up to 70% of synchronization overhead and improves running time by up to 5% for several already hand-optimized benchmarks. Thus, our automated analyses have the potential to significantly improve the performance of Java applications while enabling programmers to design simpler and more reusable multithreaded code. More... »

PAGES

19-38

References to SciGraph publications

  • 1998. Flexible alias protection in ECOOP’98 — OBJECT-ORIENTED PROGRAMMING
  • 1996. Towards alias-free pointers in ECOOP ’96 — OBJECT-ORIENTED PROGRAMMING
  • Book

    TITLE

    Static Analysis

    ISBN

    978-3-540-66459-8
    978-3-540-48294-9

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-48294-6_2

    DOI

    http://dx.doi.org/10.1007/3-540-48294-6_2

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1045898633


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "name": [
                "Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Aldrich", 
            "givenName": "Jonathan", 
            "id": "sg:person.010005345201.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010005345201.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chambers", 
            "givenName": "Craig", 
            "id": "sg:person.010633134465.58", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010633134465.58"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sirer", 
            "givenName": "Emin Gun", 
            "id": "sg:person.07757027131.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07757027131.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Eggers", 
            "givenName": "Susan", 
            "id": "sg:person.015654662057.48", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654662057.48"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/359763.359771", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002272424"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/358818.358824", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007531108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jpdc.1998.1441", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008731360"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/277650.277734", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010708918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0054091", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013914269", 
              "https://doi.org/10.1007/bfb0054091"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/236337.236344", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017698622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0053062", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023384776", 
              "https://doi.org/10.1007/bfb0053062"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/199448.199524", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027553904"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/117954.117975", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027724750"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/258915.258918", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035762217"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/319195.319198", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048409388"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.40843", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061088156"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/960116.54007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063174797"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/263698.264352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098949389"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1999-10-01", 
        "datePublishedReg": "1999-10-01", 
        "description": "This paper presents and evaluates a set of analyses designed to reduce synchronization overhead in Java programs. Monitor-based synchronization in Java often causes significant overhead, accounting for 5\u201310% of total execution time in our benchmark applications. To reduce this overhead, programmers often try to eliminate unnecessary lock operations by hand. Such manual optimizations are tedious, error-prone, and often result in poorly structured and less reusable programs. Our approach replaces manual optimizations with static analyses that automatically find and remove unnecessary synchronization from Java programs. These analyses optimize cases where a monitor is entered multiple times by a single thread, where one monitor is nested within another, and where a monitor is accessible by only one thread. A partial implementation of our analyses eliminates up to 70% of synchronization overhead and improves running time by up to 5% for several already hand-optimized benchmarks. Thus, our automated analyses have the potential to significantly improve the performance of Java applications while enabling programmers to design simpler and more reusable multithreaded code.", 
        "editor": [
          {
            "familyName": "Cortesi", 
            "givenName": "Agostino", 
            "type": "Person"
          }, 
          {
            "familyName": "Fil\u00e9", 
            "givenName": "Gilberto", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-48294-6_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-66459-8", 
            "978-3-540-48294-9"
          ], 
          "name": "Static Analysis", 
          "type": "Book"
        }, 
        "name": "Static Analyses for Eliminating Unnecessary Synchronization from Java Programs", 
        "pagination": "19-38", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-48294-6_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "daa2bf6389afb69e097ce4519fe6a06b08bea70944bfef44ee5724a45184402c"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045898633"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-48294-6_2", 
          "https://app.dimensions.ai/details/publication/pub.1045898633"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:20", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000339_0000000339/records_109493_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-48294-6_2"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48294-6_2'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48294-6_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48294-6_2'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48294-6_2'


     

    This table displays all metadata directly associated to this object as RDF triples.

    140 TRIPLES      23 PREDICATES      40 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-48294-6_2 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N6c0f955f2b804ea3a8f98e3e0c8dc837
    4 schema:citation sg:pub.10.1007/bfb0053062
    5 sg:pub.10.1007/bfb0054091
    6 https://doi.org/10.1006/jpdc.1998.1441
    7 https://doi.org/10.1109/12.40843
    8 https://doi.org/10.1145/117954.117975
    9 https://doi.org/10.1145/199448.199524
    10 https://doi.org/10.1145/236337.236344
    11 https://doi.org/10.1145/258915.258918
    12 https://doi.org/10.1145/263698.264352
    13 https://doi.org/10.1145/277650.277734
    14 https://doi.org/10.1145/319195.319198
    15 https://doi.org/10.1145/358818.358824
    16 https://doi.org/10.1145/359763.359771
    17 https://doi.org/10.1145/960116.54007
    18 schema:datePublished 1999-10-01
    19 schema:datePublishedReg 1999-10-01
    20 schema:description This paper presents and evaluates a set of analyses designed to reduce synchronization overhead in Java programs. Monitor-based synchronization in Java often causes significant overhead, accounting for 5–10% of total execution time in our benchmark applications. To reduce this overhead, programmers often try to eliminate unnecessary lock operations by hand. Such manual optimizations are tedious, error-prone, and often result in poorly structured and less reusable programs. Our approach replaces manual optimizations with static analyses that automatically find and remove unnecessary synchronization from Java programs. These analyses optimize cases where a monitor is entered multiple times by a single thread, where one monitor is nested within another, and where a monitor is accessible by only one thread. A partial implementation of our analyses eliminates up to 70% of synchronization overhead and improves running time by up to 5% for several already hand-optimized benchmarks. Thus, our automated analyses have the potential to significantly improve the performance of Java applications while enabling programmers to design simpler and more reusable multithreaded code.
    21 schema:editor Nf8e0a1664e424d5abc6630c46c598505
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree true
    25 schema:isPartOf N048387e203354a18bc66ab75dad3c029
    26 schema:name Static Analyses for Eliminating Unnecessary Synchronization from Java Programs
    27 schema:pagination 19-38
    28 schema:productId N27ff5b0c16da40059e03a3b75f60d1ac
    29 N32a114954f5e4b6982bc46a76b25fd19
    30 N75f36d68f1be40bca48977c32e73f83a
    31 schema:publisher N35d5e968ba494678882a75104bf3736b
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045898633
    33 https://doi.org/10.1007/3-540-48294-6_2
    34 schema:sdDatePublished 2019-04-16T05:20
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher Nb273470409764cc096e68094d35d8e0d
    37 schema:url https://link.springer.com/10.1007%2F3-540-48294-6_2
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N048387e203354a18bc66ab75dad3c029 schema:isbn 978-3-540-48294-9
    42 978-3-540-66459-8
    43 schema:name Static Analysis
    44 rdf:type schema:Book
    45 N262f222d7ef44f27b56ee6d659705230 rdf:first N70d01f957fda42b3995fc81851c494de
    46 rdf:rest rdf:nil
    47 N27ff5b0c16da40059e03a3b75f60d1ac schema:name dimensions_id
    48 schema:value pub.1045898633
    49 rdf:type schema:PropertyValue
    50 N32a114954f5e4b6982bc46a76b25fd19 schema:name readcube_id
    51 schema:value daa2bf6389afb69e097ce4519fe6a06b08bea70944bfef44ee5724a45184402c
    52 rdf:type schema:PropertyValue
    53 N35d5e968ba494678882a75104bf3736b schema:location Berlin, Heidelberg
    54 schema:name Springer Berlin Heidelberg
    55 rdf:type schema:Organisation
    56 N3905a545e14e4df4a4ac0db9f738cf21 rdf:first sg:person.010633134465.58
    57 rdf:rest Nf11c225f47184c74be1cb75a372d6597
    58 N413c293767fe4ed89361d0e4360851d3 schema:name Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA
    59 rdf:type schema:Organization
    60 N46173795e8814ea18a7812be69ffc210 rdf:first sg:person.015654662057.48
    61 rdf:rest rdf:nil
    62 N6c0f955f2b804ea3a8f98e3e0c8dc837 rdf:first sg:person.010005345201.27
    63 rdf:rest N3905a545e14e4df4a4ac0db9f738cf21
    64 N70d01f957fda42b3995fc81851c494de schema:familyName Filé
    65 schema:givenName Gilberto
    66 rdf:type schema:Person
    67 N75f36d68f1be40bca48977c32e73f83a schema:name doi
    68 schema:value 10.1007/3-540-48294-6_2
    69 rdf:type schema:PropertyValue
    70 N85e8dffeb1f34c4fbb7013100ae357cc schema:familyName Cortesi
    71 schema:givenName Agostino
    72 rdf:type schema:Person
    73 N8f71fbac45cf48e7903a66dbf74893bb schema:name Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA
    74 rdf:type schema:Organization
    75 Nb273470409764cc096e68094d35d8e0d schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 Ndbbce91142784999ae613c3b9be73e9d schema:name Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA
    78 rdf:type schema:Organization
    79 Nf11c225f47184c74be1cb75a372d6597 rdf:first sg:person.07757027131.87
    80 rdf:rest N46173795e8814ea18a7812be69ffc210
    81 Nf2835cd2692a465cae691762cd827e08 schema:name Department of Computer Science and Engineering, University of Washington, Box 352350, 98195, Seattle, WA, USA
    82 rdf:type schema:Organization
    83 Nf8e0a1664e424d5abc6630c46c598505 rdf:first N85e8dffeb1f34c4fbb7013100ae357cc
    84 rdf:rest N262f222d7ef44f27b56ee6d659705230
    85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Information and Computing Sciences
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Artificial Intelligence and Image Processing
    90 rdf:type schema:DefinedTerm
    91 sg:person.010005345201.27 schema:affiliation N8f71fbac45cf48e7903a66dbf74893bb
    92 schema:familyName Aldrich
    93 schema:givenName Jonathan
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010005345201.27
    95 rdf:type schema:Person
    96 sg:person.010633134465.58 schema:affiliation Ndbbce91142784999ae613c3b9be73e9d
    97 schema:familyName Chambers
    98 schema:givenName Craig
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010633134465.58
    100 rdf:type schema:Person
    101 sg:person.015654662057.48 schema:affiliation Nf2835cd2692a465cae691762cd827e08
    102 schema:familyName Eggers
    103 schema:givenName Susan
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654662057.48
    105 rdf:type schema:Person
    106 sg:person.07757027131.87 schema:affiliation N413c293767fe4ed89361d0e4360851d3
    107 schema:familyName Sirer
    108 schema:givenName Emin Gun
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07757027131.87
    110 rdf:type schema:Person
    111 sg:pub.10.1007/bfb0053062 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023384776
    112 https://doi.org/10.1007/bfb0053062
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/bfb0054091 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013914269
    115 https://doi.org/10.1007/bfb0054091
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1006/jpdc.1998.1441 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008731360
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1109/12.40843 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088156
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1145/117954.117975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027724750
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1145/199448.199524 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027553904
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1145/236337.236344 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017698622
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1145/258915.258918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035762217
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1145/263698.264352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098949389
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1145/277650.277734 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010708918
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1145/319195.319198 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048409388
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1145/358818.358824 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007531108
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1145/359763.359771 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002272424
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1145/960116.54007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063174797
    140 rdf:type schema:CreativeWork
     




    Preview window. Press ESC to close (or click here)


    ...