git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/3] Teach Git about the patience diff algorithm

From
Adeodato Simó <dato@net.com.org.es>
Date
Jan 8, 2009, 19:55 UTC
Message-ID
<20090108195511.GA8734@chistera.yi.org>
* Linus Torvalds [Fri, 02 Jan 2009 08:42:04 -0800]:
> Yes, this one is a real patience diff change, but it's also the same one 
> that I've seen in the google fanboi findings. What google did _not_ show 
> was any real-life examples, or anybody doing any critical analysis.

This comes a bit late and maybe it's redundant, but somebody just sent to a Debian mailing list a patch that was hard to read, and patience improved it. (I realize it's quite similar in spirit to the "toy patience example" that google returns, but this at list is a *real* example where patience helped me read a patch.)

I'm also attaching bzr diff output, because it's still more readable IMHO. (I realize that's independent of patience, as you explained, but I'm making a point that it'd be nice to have this addressed by somebody knowledgeable.)

Thanks,
-- 
Adeodato Simó                                     dato at net.com.org.es
Debian Developer                                  adeodato at debian.org
 
- Are you sure we're good?
- Always.
                -- Rory and Lorelai


diff --git util_sock.c util_sock.c
index e20768e..f7b9145 100644
--- util_sock.c
+++ util_sock.c
@@ -1037,40 +1037,109 @@ NTSTATUS read_data(int fd, char *buffer, size_t N)
 }
 
 /****************************************************************************
- Write data to a fd.
+ Write all data from an iov array
 ****************************************************************************/
 
-ssize_t write_data(int fd, const char *buffer, size_t N)
+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)
 {
-	size_t total=0;
-	ssize_t ret;
-	char addr[INET6_ADDRSTRLEN];
+	int i;
+	size_t to_send;
+	ssize_t thistime;
+	size_t sent;
+	struct iovec *iov_copy, *iov;
 
-	while (total < N) {
-		ret = sys_write(fd,buffer + total,N - total);
+	to_send = 0;
+	for (i=0; i<iovcnt; i++) {
+		to_send += orig_iov[i].iov_len;
+	}
 
-		if (ret == -1) {
-			if (fd == get_client_fd()) {
-				/* Try and give an error message saying
-				 * what client failed. */
-				DEBUG(0,("write_data: write failure in "
-					"writing to client %s. Error %s\n",
-					get_peer_addr(fd,addr,sizeof(addr)),
-					strerror(errno) ));
-			} else {
-				DEBUG(0,("write_data: write failure. "
-					"Error = %s\n", strerror(errno) ));
+	thistime = sys_writev(fd, orig_iov, iovcnt);
+	if ((thistime <= 0) || (thistime == to_send)) {
+		return thistime;
+	}
+	sent = thistime;
+
+	/*
+	 * We could not send everything in one call. Make a copy of iov that
+	 * we can mess with. We keep a copy of the array start in iov_copy for
+	 * the TALLOC_FREE, because we're going to modify iov later on,
+	 * discarding elements.
+	 */
+
+	iov_copy = (struct iovec *)TALLOC_MEMDUP(
+		talloc_tos(), orig_iov, sizeof(struct iovec) * iovcnt);
+
+	if (iov_copy == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+	iov = iov_copy;
+
+	while (sent < to_send) {
+		/*
+		 * We have to discard "thistime" bytes from the beginning
+		 * iov array, "thistime" contains the number of bytes sent
+		 * via writev last.
+		 */
+		while (thistime > 0) {
+			if (thistime < iov[0].iov_len) {
+				char *new_base =
+					(char *)iov[0].iov_base + thistime;
+				iov[0].iov_base = new_base;
+				iov[0].iov_len -= thistime;
+				break;
 			}
-			return -1;
+			thistime -= iov[0].iov_len;
+			iov += 1;
+			iovcnt -= 1;
 		}
 
-		if (ret == 0) {
-			return total;
+		thistime = sys_writev(fd, iov, iovcnt);
+		if (thistime <= 0) {
+			break;
 		}
+		sent += thistime;
+	}
+
+	TALLOC_FREE(iov_copy);
+	return sent;
+}
+
+/****************************************************************************
+ Write data to a fd.
+****************************************************************************/
+
+/****************************************************************************
+ Write data to a fd.
+****************************************************************************/
+
+ssize_t write_data(int fd, const char *buffer, size_t N)
+{
+	ssize_t ret;
+	struct iovec iov;
+
+	iov.iov_base = CONST_DISCARD(char *, buffer);
+	iov.iov_len = N;
+
+	ret = write_data_iov(fd, &iov, 1);
+	if (ret >= 0) {
+		return ret;
+	}
 
-		total += ret;
+	if (fd == get_client_fd()) {
+		char addr[INET6_ADDRSTRLEN];
+		/*
+		 * Try and give an error message saying what client failed.
+		 */
+		DEBUG(0, ("write_data: write failure in writing to client %s. "
+			  "Error %s\n", get_peer_addr(fd,addr,sizeof(addr)),
+			  strerror(errno)));
+	} else {
+		DEBUG(0,("write_data: write failure. Error = %s\n",
+			 strerror(errno) ));
 	}
-	return (ssize_t)total;
+
+	return -1;
 }
 
 /****************************************************************************


diff --git util_sock.c util_sock.c
index e20768e..f7b9145 100644
--- util_sock.c
+++ util_sock.c
@@ -1037,40 +1037,109 @@ NTSTATUS read_data(int fd, char *buffer, size_t N)
 }
 
 /****************************************************************************
+ Write all data from an iov array
+****************************************************************************/
+
+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)
+{
+	int i;
+	size_t to_send;
+	ssize_t thistime;
+	size_t sent;
+	struct iovec *iov_copy, *iov;
+
+	to_send = 0;
+	for (i=0; i<iovcnt; i++) {
+		to_send += orig_iov[i].iov_len;
+	}
+
+	thistime = sys_writev(fd, orig_iov, iovcnt);
+	if ((thistime <= 0) || (thistime == to_send)) {
+		return thistime;
+	}
+	sent = thistime;
+
+	/*
+	 * We could not send everything in one call. Make a copy of iov that
+	 * we can mess with. We keep a copy of the array start in iov_copy for
+	 * the TALLOC_FREE, because we're going to modify iov later on,
+	 * discarding elements.
+	 */
+
+	iov_copy = (struct iovec *)TALLOC_MEMDUP(
+		talloc_tos(), orig_iov, sizeof(struct iovec) * iovcnt);
+
+	if (iov_copy == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+	iov = iov_copy;
+
+	while (sent < to_send) {
+		/*
+		 * We have to discard "thistime" bytes from the beginning
+		 * iov array, "thistime" contains the number of bytes sent
+		 * via writev last.
+		 */
+		while (thistime > 0) {
+			if (thistime < iov[0].iov_len) {
+				char *new_base =
+					(char *)iov[0].iov_base + thistime;
+				iov[0].iov_base = new_base;
+				iov[0].iov_len -= thistime;
+				break;
+			}
+			thistime -= iov[0].iov_len;
+			iov += 1;
+			iovcnt -= 1;
+		}
+
+		thistime = sys_writev(fd, iov, iovcnt);
+		if (thistime <= 0) {
+			break;
+		}
+		sent += thistime;
+	}
+
+	TALLOC_FREE(iov_copy);
+	return sent;
+}
+
+/****************************************************************************
+ Write data to a fd.
+****************************************************************************/
+
+/****************************************************************************
  Write data to a fd.
 ****************************************************************************/
 
 ssize_t write_data(int fd, const char *buffer, size_t N)
 {
-	size_t total=0;
 	ssize_t ret;
-	char addr[INET6_ADDRSTRLEN];
+	struct iovec iov;
 
-	while (total < N) {
-		ret = sys_write(fd,buffer + total,N - total);
+	iov.iov_base = CONST_DISCARD(char *, buffer);
+	iov.iov_len = N;
 
-		if (ret == -1) {
-			if (fd == get_client_fd()) {
-				/* Try and give an error message saying
-				 * what client failed. */
-				DEBUG(0,("write_data: write failure in "
-					"writing to client %s. Error %s\n",
-					get_peer_addr(fd,addr,sizeof(addr)),
-					strerror(errno) ));
-			} else {
-				DEBUG(0,("write_data: write failure. "
-					"Error = %s\n", strerror(errno) ));
-			}
-			return -1;
-		}
-
-		if (ret == 0) {
-			return total;
-		}
+	ret = write_data_iov(fd, &iov, 1);
+	if (ret >= 0) {
+		return ret;
+	}
 
-		total += ret;
+	if (fd == get_client_fd()) {
+		char addr[INET6_ADDRSTRLEN];
+		/*
+		 * Try and give an error message saying what client failed.
+		 */
+		DEBUG(0, ("write_data: write failure in writing to client %s. "
+			  "Error %s\n", get_peer_addr(fd,addr,sizeof(addr)),
+			  strerror(errno)));
+	} else {
+		DEBUG(0,("write_data: write failure. Error = %s\n",
+			 strerror(errno) ));
 	}
-	return (ssize_t)total;
+
+	return -1;
 }
 
 /****************************************************************************


--- util_sock.c
+++ util_sock.c
@@ -1037,40 +1037,109 @@
 }
 
 /****************************************************************************
+ Write all data from an iov array
+****************************************************************************/
+
+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)
+{
+	int i;
+	size_t to_send;
+	ssize_t thistime;
+	size_t sent;
+	struct iovec *iov_copy, *iov;
+
+	to_send = 0;
+	for (i=0; i<iovcnt; i++) {
+		to_send += orig_iov[i].iov_len;
+	}
+
+	thistime = sys_writev(fd, orig_iov, iovcnt);
+	if ((thistime <= 0) || (thistime == to_send)) {
+		return thistime;
+	}
+	sent = thistime;
+
+	/*
+	 * We could not send everything in one call. Make a copy of iov that
+	 * we can mess with. We keep a copy of the array start in iov_copy for
+	 * the TALLOC_FREE, because we're going to modify iov later on,
+	 * discarding elements.
+	 */
+
+	iov_copy = (struct iovec *)TALLOC_MEMDUP(
+		talloc_tos(), orig_iov, sizeof(struct iovec) * iovcnt);
+
+	if (iov_copy == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+	iov = iov_copy;
+
+	while (sent < to_send) {
+		/*
+		 * We have to discard "thistime" bytes from the beginning
+		 * iov array, "thistime" contains the number of bytes sent
+		 * via writev last.
+		 */
+		while (thistime > 0) {
+			if (thistime < iov[0].iov_len) {
+				char *new_base =
+					(char *)iov[0].iov_base + thistime;
+				iov[0].iov_base = new_base;
+				iov[0].iov_len -= thistime;
+				break;
+			}
+			thistime -= iov[0].iov_len;
+			iov += 1;
+			iovcnt -= 1;
+		}
+
+		thistime = sys_writev(fd, iov, iovcnt);
+		if (thistime <= 0) {
+			break;
+		}
+		sent += thistime;
+	}
+
+	TALLOC_FREE(iov_copy);
+	return sent;
+}
+
+/****************************************************************************
+ Write data to a fd.
+****************************************************************************/
+
+/****************************************************************************
  Write data to a fd.
 ****************************************************************************/
 
 ssize_t write_data(int fd, const char *buffer, size_t N)
 {
-	size_t total=0;
 	ssize_t ret;
-	char addr[INET6_ADDRSTRLEN];
-
-	while (total < N) {
-		ret = sys_write(fd,buffer + total,N - total);
-
-		if (ret == -1) {
-			if (fd == get_client_fd()) {
-				/* Try and give an error message saying
-				 * what client failed. */
-				DEBUG(0,("write_data: write failure in "
-					"writing to client %s. Error %s\n",
-					get_peer_addr(fd,addr,sizeof(addr)),
-					strerror(errno) ));
-			} else {
-				DEBUG(0,("write_data: write failure. "
-					"Error = %s\n", strerror(errno) ));
-			}
-			return -1;
-		}
-
-		if (ret == 0) {
-			return total;
-		}
-
-		total += ret;
-	}
-	return (ssize_t)total;
+	struct iovec iov;
+
+	iov.iov_base = CONST_DISCARD(char *, buffer);
+	iov.iov_len = N;
+
+	ret = write_data_iov(fd, &iov, 1);
+	if (ret >= 0) {
+		return ret;
+	}
+
+	if (fd == get_client_fd()) {
+		char addr[INET6_ADDRSTRLEN];
+		/*
+		 * Try and give an error message saying what client failed.
+		 */
+		DEBUG(0, ("write_data: write failure in writing to client %s. "
+			  "Error %s\n", get_peer_addr(fd,addr,sizeof(addr)),
+			  strerror(errno)));
+	} else {
+		DEBUG(0,("write_data: write failure. Error = %s\n",
+			 strerror(errno) ));
+	}
+
+	return -1;
 }
 
 /****************************************************************************
Previous: Johannes SchindelinNext: Adeodato Simó
Message 59 of 67 in “libxdiff and patience diff”
  1. Pierre HabouzitNov 4, 2008
  2. Davide LibenziNov 4, 2008
  3. Pierre HabouzitNov 4, 2008
  4. Johannes SchindelinNov 4, 2008
  5. Pierre HabouzitNov 4, 2008
  6. Johannes SchindelinNov 4, 2008
  7. Pierre HabouzitNov 4, 2008
  8. Johannes SchindelinNov 4, 2008
  9. Pierre HabouzitNov 4, 2008
  10. 0/3 Teach Git about the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  11. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 1, 2009
  12. 2/3 Introduce the diff option '--patience'Johannes Schindelin, Jan 1, 2009
  13. 3/3 bash completions: Add the --patience optionJohannes Schindelin, Jan 1, 2009
  14. Linus TorvaldsJan 1, 2009
  15. Linus TorvaldsJan 1, 2009
  16. Johannes SchindelinJan 2, 2009
  17. Linus TorvaldsJan 2, 2009
  18. Johannes SchindelinJan 2, 2009
  19. Jeff KingJan 2, 2009
  20. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 2, 2009
  21. Johannes SchindelinJan 2, 2009
  22. Adeodato SimóJan 1, 2009
  23. Linus TorvaldsJan 2, 2009
  24. Clemens BuchacherJan 2, 2009
  25. Clemens BuchacherJan 2, 2009
  26. Linus TorvaldsJan 2, 2009
  27. Johannes SchindelinJan 2, 2009
  28. Linus TorvaldsJan 2, 2009
  29. Johannes SchindelinJan 2, 2009
  30. Jeff KingJan 2, 2009
  31. Jeff KingJan 2, 2009
  32. Jeff KingJan 2, 2009
  33. Linus TorvaldsJan 2, 2009
  34. Bazaar's patience diff as GIT_EXTERNAL_DIFFAdeodato Simó, Jan 3, 2009
  35. Johannes SchindelinJan 2, 2009
  36. Junio C HamanoJan 2, 2009
  37. Adeodato SimóJan 2, 2009
  38. Pierre HabouzitJan 6, 2009
  39. Pierre HabouzitJan 6, 2009
  40. Johannes SchindelinJan 6, 2009
  41. Pierre HabouzitJan 7, 2009
  42. Johannes SchindelinJan 7, 2009
  43. 1/3 Implement the patience diff algorithmJohannes Schindelin, Jan 7, 2009
  44. Davide LibenziJan 7, 2009
  45. Johannes SchindelinJan 7, 2009
  46. Davide LibenziJan 7, 2009
  47. Johannes SchindelinJan 7, 2009
  48. Linus TorvaldsJan 7, 2009
  49. Johannes SchindelinJan 7, 2009
  50. Davide LibenziJan 7, 2009
  51. Sam VilainJan 7, 2009
  52. Linus TorvaldsJan 7, 2009
  53. Sam VilainJan 8, 2009
  54. Johannes SchindelinJan 7, 2009
  55. Junio C HamanoJan 7, 2009
  56. Johannes SchindelinJan 7, 2009
  57. Pierre HabouzitJan 7, 2009
  58. Johannes SchindelinJan 7, 2009
  59. Adeodato SimóJan 8, 2009
  60. Adeodato SimóJan 8, 2009
  61. Junio C HamanoJan 9, 2009
  62. Johannes SchindelinJan 9, 2009
  63. Adeodato SimóJan 9, 2009
  64. Linus TorvaldsJan 9, 2009
  65. Linus TorvaldsJan 9, 2009
  66. Junio C HamanoJan 9, 2009
  67. Johannes SchindelinJan 10, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.