git DAG의 증분 선형화

Question

나는 다음의 저자이다 GitX.GitX의 기능 중 하나는 보시다시피 분기를 시각화하는 것입니다. 여기.

이 시각화는 현재 git에서 올바른 순서로 방출된 커밋을 읽어 수행됩니다.각 커밋마다 상위 항목이 알려져 있으므로 올바른 방식으로 레인을 구축하는 것이 상당히 쉽습니다.

저는 자체 커밋 풀을 사용하고 커밋을 직접 선형화하여 이 프로세스의 속도를 높이고 싶습니다.이를 통해 기존에 로드된 커밋을 재사용할 수 있고 git이 커밋을 올바른 순서로 내보낼 필요가 없기 때문에 더 빠르게 커밋을 내보낼 수 있습니다.

그러나 이를 수행하기 위해 어떤 알고리즘을 사용해야 하는지 잘 모르겠습니다.커밋을 로드하는 데 오랜 시간이 걸릴 수 있으므로(모두 표시되어야 하는 100,000개 커밋의 경우 5초 이상) 건물을 점진적으로 구축하는 것이 중요합니다.

Gitk도 같은 방식으로 진행되었으며 패치가 있습니다. 여기 구현 방법을 보여주지만 내 TCL 기술이 약하고 패치에 대한 설명이 철저하게 작성되지 않았으며 따라가기가 약간 어렵습니다.

또한 이 알고리즘은 수십만 개의 커밋을 처리해야 하므로 효율적이기를 바랍니다.또한 테이블에 표시되어야 하므로 특정 행에 빠르게 액세스하는 것이 중요합니다.

지금까지 얻은 입력, 원하는 출력 및 몇 가지 관찰 사항에 대해 설명하겠습니다.

입력:

• 커밋 ID를 커밋 개체에 매핑하는 해시 테이블 형식의 현재 커밋 풀이 있습니다.이 풀은 완료될 필요가 없습니다(모든 커밋이 필요함).
• 새 커밋이 로드될 때마다 호출할 수 있는 콜백을 사용하여 git의 새 커밋에 별도의 스레드 로드가 있습니다.커밋이 들어오는 순서는 보장되지 않지만 대부분의 경우 다음 커밋은 이전 커밋의 상위 커밋입니다.
• 커밋 객체에는 자체 개정 ID와 모든 상위 개체의 개정 ID가 있습니다.
• 나열해야 할 지점장 목록이 있습니다.즉, 표시되어야 하는 DAG의 '상단'이 하나도 없습니다.또한 단일 그래프 루트가 있을 필요는 없습니다.

산출:

• 이러한 커밋을 토폴로지 순서에 따라 선형화해야 합니다.즉, 상위 커밋이 나열된 후에는 커밋을 나열할 수 없습니다.
• 위 스크린샷에서 볼 수 있는 '분기선'도 필요합니다.대부분은 자식에 의존하므로 미리 계산해야 할 수도 있습니다.

몇 가지 참고사항:

• 커밋 목록을 재배치해야 합니다.예를 들어, 한 헤드를 다른 헤드의 조상으로 만드는 커밋이 나타날 때까지 관련 없는 커밋(브랜치 헤드)을 수행해야 할 수 있습니다.
• 여러 분기 팁이 표시되어야 합니다.
• 데이터가 로드되는 동안 최소한 부분 보기를 사용할 수 있도록 이 프로세스가 증분 방식으로 진행되는 것이 중요합니다.이는 새로운 데이터를 중간에 삽입해야 하고 분기 라인을 다시 조정해야 함을 의미합니다.

Answer 1

표준 토폴로지 정렬 is o (n) (ok, o (v+e)), 즉, 1 초 만에 메모리에 백만 개의 커밋을 정렬 할 수 있어야합니다. TCL과 같은 증분 해킹이 필요하지 않습니다.

BTW, 나는 매일 gitx를 사용하고 매일 GITX보다 훨씬 좋아 보인다. 그리고 그것에 아무런 문제가 없다 (아마도 내 저장소에 미친 합병이 없기 때문에) :)

Answer 2

좋아요, 저도 마찬가지로 해당 패치 전체를 읽는 데 어려움을 겪고 있습니다. 하지만 제가 알아낸 내용을 바탕으로 내용을 정리할 수 있는지 살펴보겠습니다.

우선, gitk는 일련의 커밋을 하나의 부모와 하나의 자식만 갖는 일련의 커밋을 포함하는 호로 압축하여 작업을 단순화합니다.다른 것 외에도 이렇게 하면 정렬을 위해 고려해야 하는 노드 수가 상당히 줄어들어 사용하는 알고리즘에 도움이 됩니다.보너스로 관련 커밋은 함께 그룹화됩니다.

이로 인해 새 커밋을 읽을 때 호를 찾는 측면에서 약간의 복잡성이 발생합니다.몇 가지 상황이 있습니다:

• 새 커밋에는 단일 상위 커밋이 있거나 상위 커밋이 없습니다.(아마도 비어 있는) 호를 확장합니다.대부분의 경우 가장 최근의 호를 확장합니다.몇 가지 흥미로운 하위 사례가 있습니다.
  • 상위에 이미 하위가 있는 경우 기존 호가 분할될 수 있습니다(예:그 부모는 분기점으로 밝혀졌는데, 미리 알지 못할 수도 있습니다.)
  • 두 개의 호를 함께 연결하는 "누락된 링크"일 수 있습니다.
  • 이 커밋에 여러 하위 항목이 있다는 것을 이미 알고 있을 수도 있습니다.
• 새 커밋에는 여러 상위 커밋(병합 커밋)이 있습니다.

다중 하위 또는 다중 상위 커밋을 호에 포함할 수도 있고 별도로 유지하는 것이 더 합리적일 수도 있습니다.어느 쪽이든 이 호 세트를 점진적으로 구축하는 것은 그리 어렵지 않습니다.

일단 이러한 호를 갖게 되면 여전히 선형화를 시도해야 합니다.귀하의 경우, 위에서 설명한 첫 번째 알고리즘 위키피디아 페이지 초기 세트 S로 사용할 알려진 분기점 세트가 있으므로 유용할 것 같습니다.

기타 참고 사항:

• 커밋 재배치는 관리 가능해야 합니다.우선, 새로운 병합 커밋, 새로 발견된 분기점 또는 두 개의 호를 하나로 결합하는 등 두 개의 호를 연결할 때만 주의하면 됩니다.주어진 호는 현재 행 번호 범위를 쉽게 유지할 수 있으므로(순차 행에 호를 배치하는 것이 괜찮다고 가정) 트리를 탐색하여 나중에 모든 새 조상이 표시되는지 확인하는 것이 매우 빠릅니다.
• 그래프 선을 그리는 것에 대해 많이 말할 수는 없지만 지금 하고 있는 것과 크게 다르지는 않을 것이라고 생각합니다.

어쨌든 도움이 되었으면 좋겠습니다.적어도 생각하는 것은 흥미로웠습니다.

Answer 3

한 번에 100k 커밋을 표시해야합니까? 어떤 종류의 사용자가 그런 종류의 정보를 흡수 할 수 있습니까?

페이징에 대해 생각해 보셨습니까? 즉, ~ 100 개의 커밋이나 무언가를 위해 계산합니다. 브랜치 라인이 뒤로 돌아 가면 (오프 페이지) Github의 배경 화살표와 같은 것을 사용하여이를 보여줄 수 있습니다.

Answer 4

나는 GITX를 사용하지 않았으므로 무언가를 놓치고있을 수도 있지만, 그래프의 몇 가지 화면을 그릴 수있을 때까지 각 현재 지점의 머리에서 아이에서 부모로 돌아갈 수있는 것 같습니다.

그것은 당신에게 이전에 루팅 된 지점의 최적의 시각적 레이아웃을 제공하지 않을 수 있습니다. 그러나 대부분의 사용자는 최근 활동에 관심이 있기 때문에 응답 성이 가장 적은 교차로가있는 그래프를 그리는 것을 기다리는 것보다 더 중요한 것 같습니다.