Tăng tuyến tính gia tăng của git DAG

Question

Tôi là tác giả của GitX. Một trong những tính năng mà GitX có là hình dung của các chi nhánh, có thể được nhìn thấy here.

Hiển thị trực quan này hiện được thực hiện bằng cách đọc các cam kết được phát ra từ git theo đúng thứ tự. Đối với mỗi cam kết, cha mẹ được biết, vì vậy nó khá dễ dàng để xây dựng các làn đường một cách chính xác.

Tôi muốn tăng tốc quá trình này bằng cách sử dụng nhóm cam kết của chính mình và tự tinh chỉnh các cam kết. Điều này cho phép tôi sử dụng lại các cam kết đã tải hiện có và cho phép git phát ra các cam kết nhanh hơn vì nó không phải phát ra chúng theo đúng thứ tự.

Tuy nhiên, tôi không chắc chắn thuật toán nào sẽ sử dụng để thực hiện việc này. Điều quan trọng là tòa nhà đang tăng dần, vì việc tải các cam kết có thể mất một thời gian dài (> 5 giây cho 100.000 cam kết, tất cả sẽ được hiển thị).

Gitk đã đi theo cùng một cách, và có một bản vá here cho thấy cách nó được triển khai, nhưng kỹ năng TCL của tôi yếu và bản vá không được nhận xét kỹ lưỡng và khó thực hiện.

Tôi cũng muốn thuật toán này hiệu quả vì nó sẽ phải xử lý hàng trăm nghìn cam kết. Nó cũng phải được hiển thị trong một bảng, vì vậy điều quan trọng là truy cập vào các hàng cụ thể là nhanh.

Tôi sẽ mô tả đầu vào mà tôi có cho đến nay, kết quả đầu ra mà tôi muốn và một vài quan sát.

Input:

• Tôi có một hồ bơi hiện các cam kết theo hình thức một bảng băm mà các bản đồ cam id cam kết đối tượng. Hồ bơi này không phải hoàn thành (có tất cả các cam kết cần thiết)
• Tôi có một chuỗi tải riêng biệt trong các cam kết mới từ git, với một cuộc gọi lại có thể được gọi mỗi khi một lần commit mới được nạp. Không có trật tự được bảo đảm trong đó các cam kết đi vào, nhưng trong hầu hết các trường hợp, cam kết tiếp theo là một phụ huynh của cam kết trước đó.
• Đối tượng cam kết có id sửa đổi của riêng nó và các id sửa đổi của tất cả các bậc cha mẹ của nó
• Tôi có một danh sách các trưởng chi nhánh cần được liệt kê. Đó là, không có một 'đầu' của DAG sẽ được hiển thị. Cũng không cần phải là một gốc đồ thị đơn.

Output:

• tôi sẽ cần phải linearize những cam kết nhằm topo. Đó là, một cam kết không thể được liệt kê sau khi cha mẹ của nó đã được liệt kê.
• Tôi cũng cần 'đường nhánh' có thể được nhìn thấy trong ảnh chụp màn hình ở trên. Đây có thể cần phải được precomputed như hầu hết trong số họ phụ thuộc vào con cái của họ.

Một vài nhận xét:

• Đó là cần thiết để di chuyển một danh sách các cam kết. Ví dụ, chúng ta có thể phải cam kết (người đứng đầu chi nhánh) không liên quan, cho đến khi một cam kết xuất hiện mà làm cho một đầu một tổ tiên của người khác.
• Nhiều mẹo chi nhánh phải được hiển thị
• Điều quan trọng là quá trình này gia tăng, do đó ít nhất một chế độ xem có sẵn trong khi dữ liệu vẫn đang tải. Điều này có nghĩa là dữ liệu mới phải được chèn vào giữa chừng và các đường nhánh phải được điều chỉnh lại.

Answer 1

Chuẩn topological sort là O (n) (OK, O (V + E)), nghĩa là bạn có thể sắp xếp một triệu commit trong bộ nhớ trong một phần giây. Không có hack gia tăng như những người trong Tcl là cần thiết.

BTW, tôi sử dụng GitX (trông tốt hơn nhiều so gitk trên OS X) hàng ngày và không có bất kỳ vấn đề với nó (có lẽ bởi vì tôi không có những hòa trộn điên trong kho của tôi) :)

Answer 2

Tôi chưa sử dụng GitX, vì vậy có thể tôi đang thiếu thứ gì đó, nhưng có vẻ như bạn có thể quay lại từ con đến cha mẹ từ đầu mỗi nhánh hiện tại cho đến khi bạn có thể vẽ một vài màn hình của biểu đồ.

Điều đó có thể không cung cấp cho bạn bố cục hình ảnh tối ưu của các nhánh được bắt nguồn từ trước đó. Nhưng có vẻ như sự đáp ứng sẽ quan trọng hơn là chờ đợi để vẽ một đồ thị với các giao cắt ít nhất, vì hầu hết người dùng có thể quan tâm đến hoạt động gần đây.

Answer 3

OK, vì vậy tôi có một thời gian khó khăn tương tự đọc toàn bộ bản vá đó, nhưng hãy xem liệu tôi có thể ghép nó lại với nhau từ những gì tôi đã tìm ra không.

Để bắt đầu, gitk đơn giản hoá mọi thứ bằng cách cô đặc một chuỗi cam kết thành một cung, chứa một loạt các cam kết mà mỗi người chỉ có một phụ huynh và một đứa con. Ngoài bất cứ điều gì khác, làm điều này nên cắt giảm khá đáng kể về số lượng các nút bạn phải xem xét cho sắp xếp của bạn, mà sẽ giúp đỡ bất kỳ thuật toán bạn sử dụng. Là phần thưởng, các cam kết có liên quan sẽ kết thúc với nhau.

Điều này giới thiệu một số phức tạp về việc tìm một vòng cung khi bạn đọc một cam kết mới. Có một vài trường hợp:

• Cam kết mới có cha hoặc mẹ hoặc không có cha mẹ. Nó mở rộng một vòng cung (có thể trống). Hầu hết thời gian, bạn sẽ chỉ mở rộng vòng cung gần đây nhất. Có một vài trường hợp thú vị:
  • Nó có thể khiến một vòng cung hiện tại bị tách ra, nếu bố mẹ của nó đã có con (tức là bố mẹ nó trở thành điểm nhánh mà tôi thu thập mà bạn không biết trước thời gian).
  • Nó có thể là "liên kết bị thiếu" kết nối hai vòng cung với nhau.
  • Bạn có thể đã biết rằng điều này cam kết có nhiều trẻ em
• mới cam kết có nhiều cha mẹ (một hợp nhất cam kết).

Bạn có thể muốn bao gồm cam kết nhiều con hoặc nhiều phụ huynh trong vòng cung hoặc có thể có ý nghĩa hơn để giữ riêng biệt chúng. Dù bằng cách nào, nó không phải là quá khó khăn để xây dựng bộ này của vòng cung tăng dần.

Khi bạn có các vòng cung này, bạn vẫn còn lại với cố gắng tuyến tính hóa chúng. Trong trường hợp của bạn, thuật toán đầu tiên được mô tả ở trên Wikipedia page có vẻ hữu ích, vì bạn có một tập hợp các điểm chi nhánh được sử dụng làm bộ S.

ghi chú khác:

• cam kết Thay đổi địa điểm nên dễ quản lý. Trước hết, bạn chỉ phải quan tâm khi bạn kết nối hai vòng cung, hoặc thông qua một cam kết hợp nhất mới, một điểm chi nhánh mới được phát hiện, hoặc kết hợp hai vòng cung thành một. Bất kỳ vòng cung nào cũng có thể dễ dàng duy trì phạm vi số hàng hiện tại của nó (giả sử bạn có thể đặt vòng cung trên các hàng tuần tự), vì vậy duyệt qua cây kiểm tra xem tất cả tổ tiên mới hiển thị sau này có khá nhanh không.
• Tôi không biết đủ để nói nhiều về việc vẽ các đường đồ thị, nhưng tôi tưởng tượng nó sẽ không quá khác so với những gì bạn làm bây giờ.

Dù sao, tôi hy vọng điều đó sẽ hữu ích. Nó là thú vị để suy nghĩ về, ít nhất.

Answer 4

Bạn có thực sự cần hiển thị 100k lần commit cùng một lúc không? Loại người dùng nào có thể hấp thụ loại thông tin đó?

Bạn đã từng nghĩ về phân trang chưa? Tôi chỉ tính toán cho ~ 100 cam kết hoặc một cái gì đó. Nếu một nhánh rẽ ngược dòng (off-page), bạn có thể sử dụng một cái gì đó giống như mũi tên chỉ trỏ của Github để chỉ ra điều đó.