Đôi điều về LongAdder trong java 8
java 8
5
Java
77
high concurrency programming
2
White

Nguyễn Hồng Phúc viết ngày 09/11/2016

Giới thiệu về LongAdder

LongAdder Là một class được implement từ java 8, hoạt động giống như AtomicLong (bắt đầu từ java 7), tuy nhiên hiệu năng thì cao hơn trong trường hợp có nhiều thread (multi-thread).
(c.f. http://blog.palominolabs.com/2014/02/10/java-8-performance-improvements-longadder-vs-atomiclong/)

Implementation

Source code: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/7b4721e4edb4/src/share/classes/java/util/concurrent/atomic/LongAdder.java

LongAdder được implement dựa trên 2 thành phần chính là Striped64Cell.

Striped64

Striped64 là base của các class có chức năng giống với LongAdder trong package java.util.concurrency.atomic.*. (Striped64 được implement bắt đầu từ java 8)

Ý tưởng cơ bản của Striped64 là nó sẽ giữ hash table of Cells (với mỗi cell có thể coi là một AtomicLong). Khi 2 threads cùng thay đổi 1 giá trị, các thread sẽ add value vào các cell khác nhau trong hash table nói trên. Nhờ vậy mà sự cạnh tranh của 2 thread được giảm xuống thấp nhất có thể.

Cách Cell update giá trị một các atomic và thread-safe

Cells là các building blocks của một Striped64. Các Cell sử dụng chiến thuật Padded variant (tấm đệm) để tăng cường tính đồng thời (high concurrency) khi cập nhật giá trị, và hỗ trợ cho việc access vào sun.misc.Unsafe.compareAndSwap (wrapped by cas).
(Một số implement khác thì gọi là compare and set: https://github.com/ruby-concurrency/thread_safe/blob/b9d94d3bbfe515947fdd1c1d83d49e6577d0234a/lib/thread_safe/util/striped64.rb#L75)

Một Cell được implement như sau:

// Source lấy từ openjdk
static final class Cell {
    volatile long p0, p1, p2, p3, p4, p5, p6;
    volatile long value;
    volatile long q0, q1, q2, q3, q4, q5, q6;
    Cell(long x) { value = x; }

    final boolean cas(long cmp, long val) {
        return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
    }

    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long valueOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> ak = Cell.class;
            valueOffset = UNSAFE.objectFieldOffset
                (ak.getDeclaredField("value"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

Ở đoạn code trên, thứ ta cần quan tâm nhất là giá trị value.
value sẽ được update bằng hàm cas: compare and swap. cas gọi tới compareAndSwapLong(...) là một hàm được cung cấp bởi thư viện Unsafe.

Các phương thức Unsafe.compareAndSwap là atomic. Được thực hiện như sau:

  1. Lấy con trỏ (pointer) của một chunk of memory (ở implement trên là gồm có thisvalueOffset đang trỏ tới cùng một giá trị value).
  2. Nếu JVM thấy rằng: value = compare value, JVM sẽ lưu swap value vào địa chỉ bộ nhớ (this & valueOffset) và return true.

Giải thích thêm về các thành phần
Unsafe cung cấp các interface để truy cấp tới vùng quản lý bộ nhớ trong JVM: memory can be allocated, overwritten, and cast)
Xem thêm: Java Magic part 4

Các volatile long được sử dụng cho duy nhất một mục đích là padding.
Padding là chiến thuật giúp ta giảm thiểu xung đột trong CPU cache bằng cách chắc chắn rằng các cells khác nhau sẽ không bao giờ được nằm trên cùng một cache line.

Padding is a strategy to reduce CPU cache contention by trying to make sure that different cells do not land in the same cache line. It has been found to bring significant performance improvements.

Implement LongAdder API

LongAdder.add(long x)

Thêm một giá trị x vào giá trị hiện tại:

Hàm LongAdder.add implement như sau:

// Source lấy từ openjdk
1. public void add(long x) {
2.     Cell[] as; long b, v; int m; Cell a;
3.     if ((as = cells) != null || !casBase(b = base, b + x)) {
4.         boolean uncontended = true;
5.         if (as == null || (m = as.length - 1) < 0 ||
6.             (a = as[getProbe() & m]) == null ||
7.             !(uncontended = a.cas(v = a.value, v + x)))
8.             longAccumulate(x, null, uncontended);
9.     }
}

Chiến thuật cơ bản trong Striped64 là: ta sẽ update vào một base value duy nhất, cho tới khi gặp xung đột đầu tiên.
Sau đó, Striped64 sẽ maintain hash table của Cells nhắm tránh xảy ra xung đột giữa các cells.

Đoạn code được thực hiện như sau:

  1. (line 3) Nếu (as = cells) != null là true nghĩa là trước đó đã xảy ra xung đột. Tới bước 3
  2. (line 3) Nếu 1 false (trước đó chưa có xung đột), thực hiện tăng thêm x: casBase(b = base, b + x). Nếu thành công: Done. Còn không thì tiếp tục
  3. (line 5) Trong trường hợp có xung đột, nếu không tồn tại hash table cells trước đó as == null || (m = as.length - 1) < 0 là true (gặp trường hợp xung đột lần đầu tiên). Tới bước 6.
  4. (line 6) Nếu thread hiện tại không chứa bất kì giá trị nào trong hash table, tới bước 6 (getProbe() trả lại hash value cho thread hiện tại)
  5. (line 7) Thử CAS: compare and swap hash table entry. Nếu true -> thành công, otherwise xảy ra xung đột và tiếp tục bước 6
  6. (line 8) longAccumulate(x, null, uncontended): Method sẽ maintain hash table. Nó sẽ tạo hash table nếu cần thiết, double size của hash table khi xảy ra xung đột, nhằm làm cho thời gian xảy ra xung đột nhỏ nhất có thể. Cuối cùng, longAccumulate thực hiện add value vào một trong các cells. (logic của longAccumulate khá phức tạp, vì vậy mình sẽ không bàn ở bài viết này).

long LongAdder.sum()

Là hàm lấy giá trị hiện tại của long adder. (Lấy tổng base và tất cả các giá trị trong cells cell.value)

Hàm sum được implement như sau:

// Source lấy từ openjdk
public long sum() {
    Cell[] as = cells; Cell a;
    long sum = base;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}
  1. Hàm trên khá đơn giản, đầu tiên sum được gán bằng giá trị base.
  2. Nếu có xung đột xảy ra (as != null) thì thêm tổng của cell.value vào base.
  3. Ngược lại, sum == base.
Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Nguyễn Hồng Phúc

9 bài viết.
41 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
36 9
Một số vấn đề Theo cá nhân tôi, Javascript có lẽ là một trong những ngôn ngữ dễ học, dễ viết nhất. Một web developer mới bắt đầu có lẽ chỉ cần từ ...
Nguyễn Hồng Phúc viết 3 năm trước
36 9
White
16 2
Mở đầu Có lẽ hầu hết những người sử dụng Linux đều biết quyền hạn của 1 file hay folder được đại diện bởi r (read), w (write), x (execute) như hìn...
Nguyễn Hồng Phúc viết hơn 3 năm trước
16 2
White
16 4
Mở đầu Ở (Link), tôi đã tổng kết lại một số nguyên tắc của câu lệnh điều kiện if, phép so sánh == và ===. Chúng ta hãy cùng bắt đầu phần 2 với điề...
Nguyễn Hồng Phúc viết 3 năm trước
16 4
Bài viết liên quan
White
14 0
LongAdder sử dụng để làm gì LongAdder xuất hiện từ JDK 8, với mục đích phục vụ bạn đếm một cái gì đó, cũng giống như chức năng tăng/giảm giá trị ...
Linh Tran Tuan viết 26 ngày trước
14 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
9 bài viết.
41 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!