Bản đồ máy tính: giá trị tính toán trước thời hạn

Question

Tôi có một computing map (với soft values) mà tôi đang sử dụng để lưu vào bộ nhớ cache kết quả của việc tính toán tốn kém.

Bây giờ tôi có một tình huống mà tôi biết rằng một khóa cụ thể có thể sẽ được tìm kiếm trong vài giây tới. Chìa khóa đó cũng đắt hơn tính toán nhiều nhất.

Tôi muốn tính toán giá trị trước, trong chuỗi ưu tiên tối thiểu để khi giá trị cuối cùng được yêu cầu, nó sẽ được lưu trong bộ nhớ cache, cải thiện thời gian phản hồi.

một cách tốt để làm là gì này như vậy mà:

1. tôi có thể kiểm soát các chủ đề (đặc biệt ưu tiên của nó), trong đó việc tính toán được thực hiện.
2. Tránh làm việc trùng lặp, tức là tính toán chỉ được thực hiện một lần. Nếu nhiệm vụ tính toán đang chạy thì chuỗi gọi đợi đợi nhiệm vụ đó thay vì tính toán lại giá trị (FutureTask thực hiện điều này. Với bản đồ tính toán của Guava, điều này là đúng nếu bạn chỉ gọi get nhưng không phải nếu bạn trộn nó với các cuộc gọi tới put.)
3. Phương pháp "giá trị tính toán trước" không đồng bộ và không có giá trị. Nếu một tính toán đã được tiến hành, nó sẽ trở lại ngay lập tức mà không cần đợi tính toán đó kết thúc.
4. Tránh đảo ngược ưu tiên, ví dụ: nếu chuỗi có mức độ ưu tiên cao yêu cầu giá trị trong khi luồng ưu tiên trung bình đang làm điều gì đó không liên quan nhưng nhiệm vụ tính toán được xếp hàng đợi trên chuỗi có mức độ ưu tiên thấp, thì chuỗi chủ đề ưu tiên cao không được bỏ đói. Có lẽ điều này có thể đạt được bằng cách tạm thời tăng ưu tiên của các luồng tính toán và/hoặc chạy tính toán trên chuỗi gọi.

Làm thế nào điều này có thể được phối hợp giữa tất cả các chủ đề liên quan?

---

thông tin bổ sung
Các tính toán trong ứng dụng của tôi là hình ảnh hoạt động lọc, điều đó có nghĩa họ là tất cả CPU-bound. Các hoạt động này bao gồm biến đổi affine (từ 50µs đến 1ms) và convolutions (lên đến 10ms.) Tất nhiên hiệu quả của các ưu tiên luồng khác nhau phụ thuộc vào khả năng của hệ điều hành để tránh các tác vụ lớn hơn.

Answer 1

Bạn có thể sắp xếp thực hiện "một lần duy nhất" tính toán nền bằng cách sử dụng Tương lai với Bản đồ tính toán. Tương lai đại diện cho nhiệm vụ tính toán giá trị. Tương lai được tạo ra bởi ComputedMap và cùng một lúc, được chuyển đến một ExecutorService để thực thi nền. Người thực hiện có thể được định cấu hình bằng triển khai thực hiện ThreadFactory của riêng bạn tạo các chuỗi có mức độ ưu tiên thấp, ví dụ:

class LowPriorityThreadFactory implements ThreadFactory 
{ 
    public Thread newThread(Runnable r) { 
    Tread t = new Thread(r); 
    t.setPriority(MIN_PRIORITY); 
    return t; 
    } 
} 

Khi giá trị là cần thiết, chủ đề ưu tiên cao của bạn sau đó lấy về tương lai khỏi bản đồ, và gọi phương thức get() để lấy kết quả, chờ đợi cho nó để được tính nếu cần thiết. Để tránh priority inversion bạn thêm một số mã bổ sung cho các nhiệm vụ:

class HandlePriorityInversionTask extends FutureTask<ResultType> 
{ 
    Integer priority; // non null if set 
    Integer originalPriority; 
    Thread thread; 
    public ResultType get() { 
     if (!isDone()) 
     setPriority(Thread.currentThread().getPriority()); 
     return super.get(); 
    } 
    public void run() { 
     synchronized (this) { 
     thread = Thread.currentThread(); 
     originalPriority = thread.getPriority(); 
     if (priority!=null) setPriority(priority); 
     } 
     super.run(); 
    } 
    protected synchronized void done() { 
     if (originalPriority!=null) setPriority(originalPriority); 
     thread = null; 
    } 

    void synchronized setPriority(int priority) { 
     this.priority = Integer.valueOf(priority); 
     if (thread!=null) 
      thread.setPriority(priority); 
    } 
} 

này sẽ chăm sóc của nâng cao ưu tiên của nhiệm vụ ưu tiên của thread gọi get() nếu nhiệm vụ vẫn chưa hoàn thành, và trả về ưu tiên cho các ban đầu khi tác vụ hoàn thành, bình thường hoặc cách khác. (Để giữ nó ngắn gọn, mã không kiểm tra xem mức độ ưu tiên có thực sự lớn hơn hay không, nhưng thật dễ dàng để thêm.)

Khi nhiệm vụ ưu tiên cao gọi get(), tương lai có thể chưa bắt đầu thực hiện. Bạn có thể bị cám dỗ để tránh điều này bằng cách thiết lập một giới hạn trên lớn về số lượng chủ đề được sử dụng bởi dịch vụ thực thi, nhưng điều này có thể là một ý tưởng tồi, vì mỗi luồng có thể chạy ở mức ưu tiên cao, tiêu thụ càng nhiều CPU càng tốt hệ điều hành sẽ tắt nó. Hồ bơi có thể có cùng kích thước với số lượng chuỗi phần cứng, ví dụ: kích thước hồ bơi đến Runtime.availableProcessors(). Nếu tác vụ không bắt đầu thực hiện, thay vì đợi cho người thực thi lên lịch biểu (đó là một dạng đảo ngược ưu tiên, vì chuỗi ưu tiên cao của bạn đang chờ các luồng ưu tiên thấp hoàn thành) thì bạn có thể chọn hủy nó người thi hành hiện tại và gửi lại trên một người thi hành chỉ chạy các luồng có mức ưu tiên cao.

Answer 2

Một cách phổ biến để điều phối loại tình huống này là có bản đồ có giá trị là đối tượng FutureTask. Vì vậy, ăn cắp như một ví dụ một số mã tôi đã viết từ một máy chủ web của tôi, ý tưởng quan trọng là đối với một tham số nhất định, chúng tôi thấy nếu đã có một FutureTask (có nghĩa là tính toán với tham số đó đã được lên lịch), và nếu chúng ta chờ đợi. Trong ví dụ này, chúng ta nếu không thì lịch trình tra cứu, nhưng điều đó có thể được thực hiện ở nơi khác với một cuộc gọi riêng biệt nếu đó là mong muốn:

private final ConcurrentMap<WordLookupJob, Future<CharSequence>> cache = ... 

    private Future<CharSequence> getOrScheduleLookup(final WordLookupJob word) { 
    Future<CharSequence> f = cache.get(word); 
    if (f == null) { 
     Callable<CharSequence> ex = new Callable<CharSequence>() { 
     public CharSequence call() throws Exception { 
      return doCalculation(word); 
     } 
     }; 
     Future<CharSequence> ft = executor.submit(ex); 
     f = cache.putIfAbsent(word, ft); 
     if (f != null) { 
     // somebody slipped in with the same word -- cancel the 
     // lookup we've just started and return the previous one 
     ft.cancel(true); 
     } else { 
     f = ft; 
     } 
    } 
    return f; 
    } 

Về những ưu tiên chủ đề: Tôi tự hỏi nếu điều này sẽ đạt được những gì bạn nghĩ rằng nó sẽ? Tôi không hoàn toàn hiểu điểm của bạn về việc nâng cao mức độ ưu tiên của việc tra cứu phía trên chuỗi chờ: nếu chuỗi đang chờ, sau đó nó chờ, bất kể ưu tiên tương đối của các chủ đề khác ... (Bạn có thể muốn xem một số bài viết tôi đã viết trên thread priorities và thread scheduling, nhưng để cắt một câu chuyện dài ngắn, tôi không chắc chắn rằng việc thay đổi mức độ ưu tiên sẽ nhất thiết phải mua cho bạn những gì bạn mong đợi.)

Answer 3

Tôi nghi ngờ rằng bạn đang hướng xuống sai đường dẫn bằng cách tập trung vào ưu tiên luồng.Thông thường các dữ liệu mà một bộ nhớ cache giữ là tốn kém để tính toán do I/O (out-of-bộ nhớ dữ liệu) so với CPU bị ràng buộc (tính toán logic). Nếu bạn đang tìm nạp trước để đoán hành động tương lai của người dùng, chẳng hạn như xem email chưa đọc, thì điều đó cho tôi biết rằng công việc của bạn có thể bị ràng buộc bởi I/O. Điều này có nghĩa là miễn là nạn đói không xảy ra (các trình lên lịch không cho phép), việc chơi các trò chơi có ưu tiên luồng sẽ không mang lại nhiều cải thiện về hiệu suất.

Nếu chi phí là cuộc gọi I/O thì chuỗi nền bị chặn đang chờ dữ liệu đến và xử lý dữ liệu đó phải khá rẻ (ví dụ: deserialization). Vì thay đổi về mức độ ưu tiên của luồng sẽ không cung cấp nhiều tốc độ, nên việc thực hiện công việc không đồng bộ trên nền threadpool là đủ. Nếu hình phạt bộ nhớ cache bỏ lỡ quá cao, thì việc sử dụng nhiều lớp bộ nhớ đệm có xu hướng giúp giảm thêm thời gian chờ của người dùng.

Answer 4

Để thay thế cho các ưu tiên của chuỗi, bạn chỉ có thể thực hiện tác vụ có mức ưu tiên thấp nếu không có tác vụ có mức độ ưu tiên cao nào đang được tiến hành. Đây là một cách đơn giản để làm điều đó:

AtomicInteger highPriorityCount = new AtomicInteger(); 

void highPriorityTask() { 
    highPriorityCount.incrementAndGet(); 
    try { 
    highPriorityImpl(); 
    } finally { 
    highPriorityCount.decrementAndGet(); 
    } 
} 

void lowPriorityTask() { 
    if (highPriorityCount.get() == 0) { 
    lowPriorityImpl(); 
    } 
} 

Trong trường hợp sử dụng của bạn, cả hai Impl() phương pháp sẽ gọi get() trên bản đồ máy tính, highPriorityImpl() trong cùng một thread và lowPriorityImpl() trong một thread khác .

Bạn có thể viết phiên bản tinh vi hơn để ngăn các tác vụ có mức ưu tiên thấp cho đến khi các tác vụ có mức độ ưu tiên cao hoàn thành và giới hạn số lượng tác vụ có mức độ ưu tiên thấp đồng thời.