From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Alex Gramiak Newsgroups: gmane.emacs.devel Subject: Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...}) Date: Sat, 20 Apr 2019 12:18:01 -0600 Message-ID: <87bm107d7q.fsf@gmail.com> References: <8736md90v0.fsf@gmail.com> <83lg05b1jk.fsf@gnu.org> <87lg047h9n.fsf@gmail.com> <83y344a97a.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="131821"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.2 (gnu/linux) Cc: emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Apr 20 20:18:28 2019 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hHuZC-000Y2B-JZ for ged-emacs-devel@m.gmane.org; Sat, 20 Apr 2019 20:18:22 +0200 Original-Received: from localhost ([127.0.0.1]:44088 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hHuZB-0002AO-K0 for ged-emacs-devel@m.gmane.org; Sat, 20 Apr 2019 14:18:21 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:51030) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hHuZ5-0002AA-V1 for emacs-devel@gnu.org; Sat, 20 Apr 2019 14:18:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hHuZ4-0004dn-Tw for emacs-devel@gnu.org; Sat, 20 Apr 2019 14:18:15 -0400 Original-Received: from mail-pg1-x535.google.com ([2607:f8b0:4864:20::535]:34449) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1hHuZ4-0004dc-OW; Sat, 20 Apr 2019 14:18:14 -0400 Original-Received: by mail-pg1-x535.google.com with SMTP id v12so4038441pgq.1; Sat, 20 Apr 2019 11:18:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=6yxRyhE5B587vYfYQxXEsl3RKDRq+U/DSbhspRP9otE=; b=XjZR50ijZ9cR1TNzln3FGj9xdi8Kmkv1yJribeuR4LNJ4iNsehK2e4UNgugscq/Bbs iL3kRGuIp0mJ6dcaZgJEqNWujUlqJ5G+n3DXjnIl0QB+Monn/NJSliOVwbX+sOymSnw3 LY6R2oEGBAOGZdHXiQOfXhSZKWoNmwzbVOYfjV9r0/yIPWPpRpKdU0JiKKsLQrMGgMze johKfR/d0Zg55oWihaSd7g0X3EkZye8cQymGTeZY41VEjH34Iv48EVtxClTP1cdyWeYb K9U1JrmjpY0JbmyVdIZL723gYK3KRuvrLF17DDY7wLL0eLl0KUuHNd9jyKn4pyg1fvGJ Vf2w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=6yxRyhE5B587vYfYQxXEsl3RKDRq+U/DSbhspRP9otE=; b=E+IZ5XqVaTDG+IxBbTpA3tA2XGRHRdxXEltURUbldTdomXakm8uIMwoG+cKBqC0uGy G/IKlEjPU6FeAt+eqsbwZ0bR5c+iSiz3CVkCcixBm+CZJLWFpUdL1YHssVp4HmnwfIcB qqIevHRce/v9ZlNlRUGTOrPPnvEKcuJGnIPrTPesilKA3j1BTMQyHebgdaap0HJn2xLN 5UZHgx7M5whflUOOMgyIYxGkV4RGr2FF3UhqQOwFin/+B+jfRSTjIBi5pP1+0f9q4HRG NvZuv96VHpVXAyQXpAHnr1onJed3h6i7a6XfcpXXKNKMiXcTkGGIQHwMyYkHQfnV77w9 0Pnw== X-Gm-Message-State: APjAAAXjxFQdkhZmvjvXpOG/2AXlaPwuJUZuOGH1KglS2qVzgwWZk9nX sINlln1VG39xFaUnBVTnOOnjoI9R X-Google-Smtp-Source: APXvYqyK7Jbx9nDtWYg2GzQVqctbdgMDf5FXn1A5+fwk7Kvsg8bmr3dVqS7aEN4zl0Q0AlmgEYUaow== X-Received: by 2002:aa7:83d1:: with SMTP id j17mr11094735pfn.78.1555784293470; Sat, 20 Apr 2019 11:18:13 -0700 (PDT) Original-Received: from lylat ([2604:3d09:e37f:1500:1a72:4878:e793:7302]) by smtp.gmail.com with ESMTPSA id n11sm8214052pgq.8.2019.04.20.11.18.11 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 20 Apr 2019 11:18:12 -0700 (PDT) In-Reply-To: <83y344a97a.fsf@gnu.org> (Eli Zaretskii's message of "Sat, 20 Apr 2019 20:16:25 +0300") X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::535 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:235707 Archived-At: Eli Zaretskii writes: > Isn't seq-position the equivalent of vector-index? It's quite similar (I forgot that it took an optional predicate), though seq-position takes a 2-arg procedure that's supposed to check for equality, while vector-index takes a 1-arg procedure. One can implement one in terms of the other. > Anyway, if some algorithms are missing from seq.el, maybe we should > just add them there instead of starting an entirely new family of > primitives? Ideally. Though in the case of vector-partition the size of the 2 partition vectors is not known in advance, so a Lisp implementation would have to create two extra Lisp vectors as opposed to using SAFE_ALLOCA. That is, unless Elisp grows a growable/resizeable vector type (which is something I was thinking about -- would that be denied?). >> > As for speed, did you have any application where the speed of the Lisp >> > implementation was inadequate? >> >> For vector-memq, the Lisp implementations almost disallow it from being >> used over memq/lists. The equivalent in seq.el, seq-position, is ~100x >> slower for smaller vectors and ~200x for larger (500 elements) vectors. > > The factors don't really answer my question. The question was whether > some real-life application that uses seq.el is so slow that moving > them to C is necessary. IOW, the question was about absolute times, > not relative times. If you can describe such use cases, I'd like to > discuss them with the participation of seq.el's maintainer first. Currently the only (M)ELPA package I use that depends on seq is Flycheck, that doesn't seem to use seq with vectors. >> The main two I care about here are vector-memq/vector-member. > > Please tell why in more detail. Well, it's a stupid itch, but sometimes I see the (memq elt ) and think that using a vector would be faster/better, mainly since memq has to check for cycles. More generally, there's currently no way to check existence in a vector nearly as fast as one can check existence in a list, which is unusual in programming languages. This unfairly discourages usage of vectors in appropriate places. I don't believe that the vector-memq/member procedures would pose a maintenance burden like some of the others (vector-apply in particular) would.