From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Tue, 21 Feb 2017 07:56:43 +0100 Message-ID: <87vas4owus.fsf@luca> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> <87vasr5tqd.fsf@hochschule-trier.de> <87d1ex4kon.fsf@hochschule-trier.de> <87d1evod6x.fsf@fastmail.com> <877f53ftab.fsf@hochschule-trier.de> <878tpiqiuc.fsf@hochschule-trier.de> <87shnppspb.fsf@hochschule-trier.de> <87o9yc9v30.fsf@hochschule-trier.de> <87a89vaes3.fsf@hochschule-trier.de> <87efz7n0g5.fsf@fastmail.com> <877f4uah6i.fsf@hochschule-trier.de> <83k28u1uyz.fsf@gnu.org> <871suxs9ad.fsf@hochschule-trier.de> <837f4pxpdc.fsf@gnu.org> <877f4lls9e.fsf@hochschule-trier.de> <838tp0q3k8.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1487660261 4163 195.159.176.226 (21 Feb 2017 06:57:41 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 21 Feb 2017 06:57:41 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) Cc: joakim.jalap@fastmail.com, monnier@iro.umontreal.ca, emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Feb 21 07:57:37 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cg4OB-0000HQ-Od for ged-emacs-devel@m.gmane.org; Tue, 21 Feb 2017 07:57:31 +0100 Original-Received: from localhost ([::1]:42613 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cg4OH-0006X1-Jd for ged-emacs-devel@m.gmane.org; Tue, 21 Feb 2017 01:57:37 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56144) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cg4Nl-0006Wi-UU for emacs-devel@gnu.org; Tue, 21 Feb 2017 01:57:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cg4Nk-0003ba-Vj for emacs-devel@gnu.org; Tue, 21 Feb 2017 01:57:05 -0500 Original-Received: from gateway-a.fh-trier.de ([143.93.54.181]:60279) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cg4Nf-0003as-Hv; Tue, 21 Feb 2017 01:56:59 -0500 X-Virus-Scanned: by Amavisd-new + McAfee uvscan + ClamAV [Rechenzentrum Hochschule Trier (RZ/HT)] Original-Received: from localhost (ip5f5bdeea.dynamic.kabel-deutschland.de [95.91.222.234]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: politza) by gateway-a.fh-trier.de (Postfix) with ESMTPSA id D8E4A179ADE8; Tue, 21 Feb 2017 07:56:43 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=hochschule-trier.de; s=default; t=1487660204; bh=oT8A6WDwr+vG3DzAZvwulEOOxMc=; h=From:To:Cc:Subject:References:Date:In-Reply-To:Message-ID: MIME-Version:Content-Type; b=lHGbf4YYlnEVP6iPAvhrQL7bTnEEfKM+fXoN9yn1/r/Y0CwHCsEBWZ9Tf0hOLQ2F0 Lq/ZtTC+VE9wYC+g+iofGb4KyRp7EBAsBbOirhsHsnLPHBktkS0xqgH9s/gX/+Ps/4 mOxsBOR+IL8gso6eQYsEBWCa2vNO2Ewqe+wnhxVs= In-Reply-To: <838tp0q3k8.fsf@gnu.org> (Eli Zaretskii's message of "Mon, 20 Feb 2017 17:34:15 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x [fuzzy] X-Received-From: 143.93.54.181 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:212519 Archived-At: Eli Zaretskii writes: >> +------------------------+-----+------+ >> |2500 overlays |tree |list | >> +------------------------+-----+------+ >> |sequential/face/scroll |1.28 |1.32 | >> +------------------------+-----+------+ >> |hierarchical/face/scroll|76.59|174.64| >> +------------------------+-----+------+ > > The new implementation is still faster than the old one, so perhaps > you shouldn't bother too much? Or am I missing something? Well, if my implementation were to be, for example, twice as fast as the current one for every operation, that would still be to slow. There is absolute run-time and then there is growth rate. What you should comparing is the first with the second line, any column will do. It's a factor of >50 and the difference between m*log(n) and m*n (with m being the number of "scrolled lines" and n the number of overlays.) The only difference here is the way these overlays were layed out. Ideally, I think, this last detail should be of no consequence and the implementation should only be limited by the number of overlays and not by where in the buffer they occur. But, yes, I shouldn't worry so much. I also missed an important detail: After we determined the next overlay change, we most likely are going to examine the overlays properties at that position. And this would require examining all n overlays (in the "hierarchical" scenario) anyway, thus the complexity of the operation as a whole would not change, if next-overlay-change were to be faster. I think I'm going to relax now. -ap