Tại sao hiệu suất của tôi chậm lại khi thu thập dữ liệu, tôi di chuyển các phương thức vào một lớp cơ sở?

Question

Tôi đang viết các triển khai khác nhau của cây nhị phân bất biến trong C#, và tôi muốn cây của tôi kế thừa một số phương thức phổ biến từ một lớp cơ sở.

Thật không may, các lớp học xuất phát từ lớp cơ sở là abysmally chậm. Các lớp không có nguồn gốc thực hiện đầy đủ. Dưới đây là hai triển khai gần như giống hệt của một cây AVL để chứng minh:

• AvlTree: http://pastebin.com/V4WWUAyT
• DerivedAvlTree: http://pastebin.com/PussQDmN

Hai cây có chính xác cùng một mã, nhưng tôi đã chuyển phương thức DerivedAvlTree.Insert trong lớp cơ sở. Dưới đây là một ứng dụng thử nghiệm:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using Juliet.Collections.Immutable; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     const int VALUE_COUNT = 5000; 

     static void Main(string[] args) 
     { 
      var avlTreeTimes = TimeIt(TestAvlTree); 
      var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree); 

      Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes); 
     } 

     static double TimeIt(Func<int, int> f) 
     { 
      var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 }; 

      var times = new List<double>(); 

      foreach (int seed in seeds) 
      { 
       var sw = Stopwatch.StartNew(); 
       f(seed); 
       sw.Stop(); 
       times.Add(sw.Elapsed.TotalMilliseconds); 
      } 

      // throwing away top and bottom results 
      times.Sort(); 
      times.RemoveAt(0); 
      times.RemoveAt(times.Count - 1); 
      return times.Average(); 
     } 

     static int TestAvlTree(int seed) 
     { 
      var rnd = new System.Random(seed); 

      var avlTree = AvlTree<double>.Create((x, y) => x.CompareTo(y)); 
      for (int i = 0; i < VALUE_COUNT; i++) 
      { 
       avlTree = avlTree.Insert(rnd.NextDouble()); 
      } 

      return avlTree.Count; 
     } 

     static int TestDerivedAvlTree(int seed) 
     { 
      var rnd = new System.Random(seed); 

      var avlTree2 = DerivedAvlTree<double>.Create((x, y) => x.CompareTo(y)); 
      for (int i = 0; i < VALUE_COUNT; i++) 
      { 
       avlTree2 = avlTree2.Insert(rnd.NextDouble()); 
      } 

      return avlTree2.Count; 
     } 
    } 
} 

• AvlTree: chèn 5000 mục trong 121 ms
• DerivedAvlTree: chèn 5000 mục trong 2182 ms

profiler tôi chỉ ra rằng chương trình dành một số tiền inordinate thời gian trong BaseBinaryTree.Insert. Bất kỳ ai quan tâm có thể thấy số EQATEC log file Tôi đã tạo bằng mã ở trên (bạn sẽ cần EQATEC profiler để hiểu rõ tệp).

Tôi thực sự muốn sử dụng một lớp cơ sở chung cho tất cả các cây nhị phân của mình, nhưng tôi không thể làm điều đó nếu hiệu suất sẽ bị ảnh hưởng.

Điều gì khiến DerivedAvlTree của tôi hoạt động quá tệ và tôi có thể làm gì để khắc phục sự cố?

Answer 1

Lưu ý - hiện tại có giải pháp "sạch" ở đây, vì vậy hãy chuyển sang bản chỉnh sửa cuối cùng nếu bạn chỉ muốn phiên bản chạy nhanh và không quan tâm đến tất cả công việc thám tử.

Dường như không có sự khác biệt giữa các cuộc gọi trực tiếp và cuộc gọi ảo gây ra sự chậm lại. Đó là một cái gì đó để làm với những đại biểu; Tôi không thể giải thích cụ thể nó là gì, nhưng nhìn vào IL tạo ra được hiển thị rất nhiều đại biểu lưu trữ mà tôi nghĩ có thể không được sử dụng trong phiên bản lớp cơ sở. Nhưng bản thân IL dường như không khác biệt đáng kể giữa hai phiên bản, điều này khiến tôi tin rằng bản thân jitter có trách nhiệm một phần.

Hãy xem refactoring này, cắt thời gian chạy khoảng 60%:

public virtual TreeType Insert(T value) 
{ 
    Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) => 
    { 
     int compare = this.Comparer(value, x); 
     if (compare < 0) { return CreateNode(l.Insert(value), x, r); } 
     else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } 
     return Self(); 
    }; 
    return Insert<TreeType>(value, nodeFunc); 
} 

private TreeType Insert<U>(T value, 
    Func<TreeType, T, TreeType, TreeType> nodeFunc) 
{ 
    return this.Match<TreeType>(
     () => CreateNode(Self(), value, Self()), 
     nodeFunc); 
} 

này nên (và dường như không) đảm bảo rằng các đại biểu chèn chỉ được tạo ra một lần mỗi chèn - nó không được tạo trên mỗi lần đệ quy. Trên máy tính của tôi, nó giảm thời gian chạy từ 350 ms xuống còn 120 ms (ngược lại, phiên bản một lớp chạy trong khoảng 30 ms, vì vậy đây vẫn là hư không gần nơi nó nên ở).

Nhưng đây là nơi nó thậm chí còn khó hơn - sau khi thử việc tái cấu trúc ở trên, tôi nghĩ, hmm, có lẽ nó vẫn còn chậm vì tôi chỉ làm một nửa công việc. Vì vậy, tôi đã cố gắng thể hóa các đại biểu đầu tiên cũng như:

public virtual TreeType Insert(T value) 
{ 
    Func<TreeType> nilFunc =() => CreateNode(Self(), value, Self()); 
    Func<TreeType, T, TreeType, TreeType> nodeFunc = (l, x, r) => 
    { 
     int compare = this.Comparer(value, x); 
     if (compare < 0) { return CreateNode(l.Insert(value), x, r); } 
     else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } 
     return Self(); 
    }; 
    return Insert<TreeType>(value, nilFunc, nodeFunc); 
} 

private TreeType Insert<U>(T value, Func<TreeType> nilFunc, 
    Func<TreeType, T, TreeType, TreeType> nodeFunc) 
{ 
    return this.Match<TreeType>(nilFunc, nodeFunc); 
} 

Và đoán những gì ... Đây đã làm cho nó chậm một lần nữa! Với phiên bản này, trên máy tính của tôi, nó mất hơn 250 ms trong lần chạy này.

Điều này bất chấp tất cả các giải thích hợp lý có thể liên quan đến vấn đề với bytecode được biên dịch, đó là lý do tại sao tôi nghi ngờ rằng jitter nằm trong âm mưu này. Tôi nghĩ rằng "tối ưu hóa" đầu tiên ở trên có thể là (CẢNH BÁO - đầu cơ trước) cho phép chèn đại biểu được inlined - đó là một thực tế được biết rằng jitter không thể gọi nội tuyến ảo - nhưng vẫn còn cái gì khác đó là không nội tuyến và đó là nơi tôi hiện đang bối rối.

Bước tiếp theo của tôi là vô hiệu hóa chọn lọc nội tuyến trên các phương thức nhất định qua MethodImplAttribute và xem hiệu ứng nào có trong thời gian chạy - điều đó sẽ giúp chứng minh hoặc bác bỏ lý thuyết này.

Tôi biết đây không phải là câu trả lời hoàn chỉnh nhưng hy vọng ít nhất nó sẽ cung cấp cho bạn một số thứ để làm việc và có thể một số thử nghiệm tiếp theo với sự phân hủy này có thể tạo ra kết quả gần với hiệu suất cho phiên bản gốc.

---

Chỉnh sửa: Hah, ngay sau khi tôi trình này, tôi loạng choạng về tối ưu hóa khác. Nếu bạn thêm phương pháp này để các lớp cơ sở:

private TreeType CreateNilNode(T value) 
{ 
    return CreateNode(Self(), value, Self()); 
} 

Bây giờ thời gian chạy giảm xuống còn 38 ms ở đây, chỉ vừa đủ so với phiên bản gốc. Điều này thổi tâm trí của tôi, bởi vì không có gì thực sự tham khảo phương pháp này! Phương thức riêng tư Insert<U> vẫn giống với khối mã đầu tiên trong câu trả lời của tôi. Tôi đã chuyển sang số để thay đổi đối số đầu tiên tham chiếu phương thức CreateNilNode, nhưng tôi không phải làm như vậy. Hoặc là jitter đang thấy rằng các đại biểu vô danh là giống như phương pháp CreateNilNode và chia sẻ cơ thể (có thể nội tuyến một lần nữa), hoặc ... hoặc, tôi không biết. Đây là ví dụ đầu tiên tôi từng chứng kiến ​​khi thêm một phương thức riêng và không bao giờ gọi nó là có thể tăng tốc một chương trình với hệ số là 4.

Bạn sẽ phải kiểm tra điều này để đảm bảo rằng tôi đã không vô tình giới thiệu bất kỳ lỗi logic nào - chắc chắn là không, mã gần như giống nhau - nhưng nếu tất cả đều kiểm tra, thì bạn ở đây, điều này chạy nhanh như không bắt nguồn từ AvlTree.

---

THÊM CẬP NHẬT

tôi đã có thể đưa ra một phiên bản của sự kết hợp cơ sở/có nguồn gốc thực sự chạy hơi nhanh so với phiên bản duy nhất lớp. Có một số coaxing, nhưng nó hoạt động!

Những gì chúng tôi cần làm là tạo một trình bổ sung dành riêng có thể tạo tất cả các đại biểu chỉ một lần mà không cần phải làm bất kỳ việc thu giữ biến nào. Thay vào đó, tất cả trạng thái được lưu trữ trong các trường thành viên. Đặt này bên trong lớp BaseBinaryTree:

protected class Inserter 
{ 
    private TreeType tree; 
    private Func<TreeType> nilFunc; 
    private Func<TreeType, T, TreeType, TreeType> nodeFunc; 
    private T value; 

    public Inserter(T value) 
    { 
     this.nilFunc =() => CreateNode(); 
     this.nodeFunc = (l, x, r) => PerformMatch(l, x, r); 
     this.value = value; 
    } 

    public TreeType Insert(TreeType parent) 
    { 
     this.tree = parent; 
     return tree.Match<TreeType>(nilFunc, nodeFunc); 
    } 

    private TreeType CreateNode() 
    { 
     return tree.CreateNode(tree, value, tree); 
    } 

    private TreeType PerformMatch(TreeType l, T x, TreeType r) 
    { 
     int compare = tree.Comparer(value, x); 
     if (compare < 0) { return tree.CreateNode(l.Insert(value, this), x, r); } 
     else if (compare > 0) { return tree.CreateNode(l, x, r.Insert(value, this)); } 
     return tree; 
    } 
} 

Vâng, vâng, tôi biết, nó rất un-chức năng sử dụng mà có thể thay đổi trạng thái nội tree, nhưng hãy nhớ rằng đây không phải là cây bản thân, nó chỉ là một không dùng nữa "Runnable "ví dụ. Không ai từng nói rằng perf-opt là khá! Đây là cách duy nhất để tránh tạo một Inserter mới cho mỗi cuộc gọi đệ quy, nếu không sẽ làm chậm điều này xuống trên tài khoản của tất cả các phân bổ mới của Inserter và các đại biểu nội bộ của nó.

Bây giờ thay thế các phương pháp chèn của lớp cơ sở như sau:

public TreeType Insert(T value) 
{ 
    return Insert(value, null); 
} 

protected virtual TreeType Insert(T value, Inserter inserter) 
{ 
    if (inserter == null) 
    { 
     inserter = new Inserter(value); 
    } 
    return inserter.Insert(Self()); 
} 

tôi đã thực hiện các công Insert phương pháp phi ảo; tất cả các công việc thực tế được giao cho một phương pháp được bảo vệ (hoặc tạo riêng của nó) Inserter ví dụ. Thay đổi lớp được thừa kế rất đơn giản đủ, chỉ cần thay thế các phương pháp ghi đè Insert với điều này:

protected override DerivedAvlTree<T> Insert(T value, Inserter inserter) 
{ 
    return base.Insert(value, inserter).Balance(); 
} 

Vậy là xong. Bây giờ chạy cái này. Nó sẽ mất gần như cùng một lượng thời gian giống như AvlTree, thường ít hơn vài phần nghìn giây trong bản phát hành bản phát hành.

Sự chậm lại rõ ràng là do một số kết hợp cụ thể của các phương pháp ảo, các phương thức ẩn danh và ghi biến số bằng cách nào đó ngăn cản jitter thực hiện tối ưu hóa quan trọng. Tôi không chắc chắn rằng nó là nội tuyến nữa, nó có thể chỉ là bộ nhớ đệm các đại biểu, nhưng tôi nghĩ rằng những người duy nhất có thể thực sự xây dựng được những người jitter jitter mình.

Answer 2

Nó không liên quan gì đến lớp dẫn xuất gọi là triển khai ban đầu và sau đó cũng gọi số dư, phải không?

Tôi nghĩ bạn có thể cần xem mã máy được tạo để xem có gì khác biệt. Tất cả những gì tôi có thể thấy từ mã nguồn là bạn đã thay đổi rất nhiều phương thức tĩnh thành các phương thức ảo được gọi là đa hình ... trong trường hợp đầu tiên JIT biết chính xác phương thức nào sẽ được gọi và có thể thực hiện lệnh gọi trực tiếp, thậm chí có thể nội tuyến. Nhưng với một cuộc gọi đa hình nó không có sự lựa chọn nào khác ngoài việc thực hiện tra cứu bảng và cuộc gọi gián tiếp. Việc tra cứu đó đại diện cho một phần đáng kể công việc đang được thực hiện.

Cuộc sống có thể tốt hơn nếu bạn gọi ((TreeType)) .Method() thay vì this.Method(), nhưng có khả năng bạn không thể loại bỏ cuộc gọi đa hình trừ khi bạn cũng khai báo các phương thức ghi đè . Và thậm chí sau đó, bạn có thể trả tiền phạt của một kiểm tra thời gian chạy trên trường hợp này.

Việc đưa mã có thể sử dụng lại vào các phương thức tĩnh chung trong lớp cơ sở cũng có thể giúp phần nào, nhưng tôi nghĩ bạn vẫn sẽ trả tiền cho các cuộc gọi đa hình. C# generics chỉ không tối ưu hóa cũng như các mẫu C++.

Answer 3

Bạn đang chạy theo IDE VS, phải không? Mất khoảng 20 lần, phải không?

Quấn vòng quanh nó để lặp lại 10 lần, vì vậy phiên bản dài sẽ mất 20 giây. Sau đó, trong khi nó đang chạy, nhấn nút "tạm dừng", và nhìn vào ngăn xếp cuộc gọi. Bạn sẽ thấy chính xác vấn đề là gì với độ chắc chắn 95%. Nếu bạn không tin những gì bạn thấy, hãy thử thêm một vài lần nữa. Tại sao nó hoạt động? Here's the long explanation và here's the short one.