From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from qmta04.westchester.pa.mail.comcast.net (qmta04.westchester.pa.mail.comcast.net [IPv6:2001:558:fe14:43:76:96:62:40]) by hurricane.the-brannons.com (Postfix) with ESMTP id 839EF778B4 for ; Tue, 11 Mar 2014 14:00:29 -0700 (PDT) Received: from omta04.westchester.pa.mail.comcast.net ([76.96.62.35]) by qmta04.westchester.pa.mail.comcast.net with comcast id cD2N1n0040ldTLk54Lz9K3; Tue, 11 Mar 2014 20:59:09 +0000 Received: from eklhad ([107.5.36.150]) by omta04.westchester.pa.mail.comcast.net with comcast id cLz91n00R3EMmQj01Lz9eT; Tue, 11 Mar 2014 20:59:09 +0000 To: Edbrowse-dev@lists.the-brannons.com From: Karl Dahlke User-Agent: edbrowse/3.5.1 Date: Tue, 11 Mar 2014 16:59:10 -0400 Message-ID: <20140211165910.eklhad@comcast.net> Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1394571549; bh=KCKoBVb9Mu9CAinlOdujx50EGvzSz4K/ZtbPvDGAx/I=; h=Received:Received:To:From:Reply-to:Subject:Date:Message-ID: Mime-Version:Content-Type; b=Gbe8CArQXoBqMPWAlJXTVKsvZ6xvTO/3AOiUhD9qCz75tNxg8MVBtQ44m936yhIH3 wB/DEdD/XAvKbv0pZtIvYNATLIAqps3+GiNr07yQCcjxY7OEK+xRnvIOM9AO3hCox8 NwjgP9XFmqIj1sGNP77sI+KKY3IptV10VkO48U56tNkvHBHXBlL3ByuyL9Foy756l7 jk/RjK1MElKsnAlT0dk5it5yBx9OJMly2ekZjBdXj0VfHxWcZxUYh6BQ+0Uobqk83z QQuGWcChGToVIHL5UaNI34ZjhEFSNYOoYCvKfDlW9YQJmRzjEbpw4mo05jDgHhpShl v3CVGrvt+rrVQ== Subject: [Edbrowse-dev] Setters and Post Scan X-BeenThere: edbrowse-dev@lists.the-brannons.com X-Mailman-Version: 2.1.17 Precedence: list Reply-To: Karl Dahlke List-Id: Edbrowse Development List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Mar 2014 21:00:29 -0000 > > perhaps growing as n^2 for the number of html tags, > Out of interest, how do you arrive at this figure? Mostly a gut feeling. As background, consider my garbage collector for lines in a buffer. This is just edits, no browsing. Make a change, then make another change, so that there are now some lines that you won't need even if you undo. How do I determine and free those lines? By comparing two maps of pointers. The pointers in A, not in B, are not needed and can be freed. The first version was simple and stupid, looking for things in A not in B, and ran in n^2 time. This didn't matter for a few years, until I started editing some really big files. You also have started editing some large files. If a file has a million lines, thatt's a trillion operations per edit. I enter a substitute command and wait 2 minutes for a response. I don't think so! So a few years ago I rewrote it using quicksort and and internal form of comm, and it is plenty quick, even for large files. Look for qsort() in buffers.c. Now fast forward to today; I am scanning a tree of js objects and comparing the tags that are implied by those objects with the tags we already have, and doing, essentially, a diff, so I can report to the user what has changed, which a sighted person would simply see as a change to something on the screen. It is very likely that there are quick ways to run this comparison, but if there absolutely aren't, and if a web page rewrote itself in a nasty way that like changed every other line, then maybe the comparison would be as awful as n^2. But as I say I expect there will be better algorithms once we really dive into it, and I'm quite sure that web pages only change small portions of themselves, the text in various boxes, or menus, etc, and don't completely rewrite themselves, so that's why I don't think it will be a performance issue, even if we implement it in a rather direct and plodding way. Karl Dahlke