3 ms·
Can someone with more domain knowledge than I comment on whether or not this project is mathematically possible? I remember the reason given for not making git
by aidenn0 6y ago
Can someone with more domain knowledge than I comment on whether or not this project is mathematically possible?
I remember the reason given for not making git patching sound was because all the sound algorithms known to the git author were slower in the common case, and only better in less common cases.
Darcs is really fast for what it does, but git is way faster by doing less.
- tom_mellior 6y agoThe actual execution time of local git commands is never noticeable in my work. The time spent cleaning up merge conflicts is very noticeable though. I could very well imagine being faster overall with a tool that runs half a second longer every time I commit, but that saves me from cleaning up cases where it couldn't figure out a merge.
- aidenn0 6y agoI find that if you spend a lot of time on conflict resolution, it may be an indication your workflow is fighting git. There is a lot of really bad advice on git workflows out there and even worse workflows in the real world. I think gitworkflow(7) should be required reading, as it explains not just how, but why the kernel uses git the way it does
- tom_mellior 6y agoDo you mean https://git-scm.com/docs/gitworkflows https://git-scm.com/docs/gitworkflows ? It doesn't seem to say anything about the kernel. Maybe you mean something else. Our workflow isn't in conflict with any of this, but some parts of our codebase evolve quickly, so topic branches regularly need to merge or rebase conflicting stuff.
- nestorD 6y agoIt is mathematicaly possible but has not been for a very long time. Darcs algorithms suffer from complexity problems that have now been theorically solved, Pijul implements those new algorithms in the hope of getting both a good runtime and better properties than git. For some resources on the underlying algorithms, see: https://pijul.org/manual/theory.html https://pijul.org/manual/theory.html
- pmeunier 6y agoExcellent question! This project is indeed mathematically possible, but did require two separate innovations: - an "engineering" one, called Sanakirja, which is a fast, forkable, transactionnal, on-disk key-value store. Although it might not be as super-fast as other database engines, it's forkable (allowing to make fast branches in Pijul). - a few "mathematical" innovations: - a good understanding of why Darcs is linearly slow in the normal case, and exponentially slow in the worst case. - some category theory to give a hint of relevant datastructures. - a few graph algorithms with just the right algorithmic complexity. - a good enough data representation for patches and repositories. (disclaimer: I'm the lead author on most of this).