From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Re: more advanced bytevector => supervectors Date: Wed, 8 Sep 2021 04:04:06 +0200 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000b338df05cb724c88" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2967"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Wed Sep 08 04:04:43 2021 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mNmx8-0000ci-Og for guile-devel@m.gmane-mx.org; Wed, 08 Sep 2021 04:04:42 +0200 Original-Received: from localhost ([::1]:40276 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mNmx6-00038B-W8 for guile-devel@m.gmane-mx.org; Tue, 07 Sep 2021 22:04:41 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:42480) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mNmwo-00035t-8h for guile-devel@gnu.org; Tue, 07 Sep 2021 22:04:22 -0400 Original-Received: from mail-pl1-x62a.google.com ([2607:f8b0:4864:20::62a]:36809) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mNmwk-00007W-Vw for guile-devel@gnu.org; Tue, 07 Sep 2021 22:04:21 -0400 Original-Received: by mail-pl1-x62a.google.com with SMTP id q21so341076plq.3 for ; Tue, 07 Sep 2021 19:04:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=9w19SBNm++iI4londtQlwSk0gbflSpcBhND7w1oPcYI=; b=iIVFPQL/rJgYvQlWEvwylUsEVTmIxE4M1A9a08ysAQIXyq0A8QJcCTAxfct6VVg3jT tpm2WeMe0IsNUalgSODKkeA2Y7zsy2gBoybreqLB1vWQ12z++H0x2TbnizPCfIy9VFta XZz3u2LBYxGRCYaFFyApvWessZw6sWl2eRkuVZD56RfSlAxmTy3anNsONtA3kR//Ic++ m2r/b7XdIBNf/Ouv/AisfwxN0hyWwQ5qu7f7+cEPiNTdQRw0fCYLk9JiZNrenEAwKEJZ aVJ4WijvK/RXqycmrXJGlrQuxBx1je8ON+W5BTqdUx3w7oLGp41My7zuYDBSU2rOKDfl 0d6A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=9w19SBNm++iI4londtQlwSk0gbflSpcBhND7w1oPcYI=; b=fdAcbJmImRaeR0pPPxZ3jGmQmgZRNWiHMQWseQA0JnEjgt0ymQHA4BK8J7SC+mch5V l1HaC1uiga/AUTESipZdZ0wjFifD/OwaFXq3YZZ2ioP+1oDqGCtvTS9EmnbG+MLxMFxH s26Cr0DhwrxOjGUm7Pp+wlgo4txpBdhJD8/iURA1kLHsAsHMv/1CW2yYqdyzu5Qk2t04 SwXHg2DcrGROqEDS99JQcyt6xCeI02JFpacRkieUfswR/Kk9aMUGN0GvY0boNp6tmfY7 Mw43TBj++fhZ4Ip2OWVS8RNQnqm0C8tccbLNg4ngfK2ESCvOS3ocHLIaD+99UVekkmSz IkAw== X-Gm-Message-State: AOAM531dmPAt3FHH9zpM9w/beEsHwwLxsmlLVecp43VKSW7VKmUC/2T1 exJhf62Pzd0XoRS3I8hDImArIIQ3VT1DxdBTdq+sdFPlZIg= X-Google-Smtp-Source: ABdhPJwxsETj28/j1gNJVG/rmXc15/29c2Sd4nacPh3F2hQhYMkHd7MchUe/NBCpZJnAaFosBa4Rt8zgcwCh6RWVNXM= X-Received: by 2002:a17:902:8c93:b0:13a:1dd7:485b with SMTP id t19-20020a1709028c9300b0013a1dd7485bmr957361plo.4.1631066657076; Tue, 07 Sep 2021 19:04:17 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::62a; envelope-from=stefan.itampe@gmail.com; helo=mail-pl1-x62a.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:20844 Archived-At: --000000000000b338df05cb724c88 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Today I added structure to support supervectors of scheme values and refactored the code with a nice macrology. So now we have an infrastructure that the compiler can compile to very efficient code. All loop must be dispatched to the type of ref and set operations. But the good part is that this selection is done only once on each bin. which can be amortised with all the work on the loop. This means that there can be an explosion in the number of combinations. The design is such that one can select the set of variants used in a nice interface. So let's discuss the setup to illustrate this point afet a small detour to algebra After investigating the structure of bit like vectors today I turned to algebraic operations and wonder about what structure we can have regarding supervectors. First to note is that storing an offset in the bin can be of value if we only consider + and - operations so for a bin with values X we store it as a + X, now adding (a1 + X1) + (a2 + X2) lead to the final value (a1 + a2) + (X1 + X2) which means that a1 and a2 can be general values and we could try to compress the X1 and X2 to a smaller byte structure For multiplication we can have a scaling operation and if we only conisder * / we have (b1 * X1) * (b2 * X2) =3D (b1*b2) (X1*X2) Mixing multiplications will lead to problems but essentially if you add number you can gain if the scaling is the same e.g. (a1 + bX1) + (a2 + b*X2) =3D (a1 + a2) + b (X1 + X2). complexity wise one do not win here, but the X1 and X2 could be one type of number and the scale and offset of a larger type. All operations + - * / of a constant bin with a fat bin can be fast if we store a scaling and an offset. This is the basic structure when considering basic algebra and one could possibly benefit by storing and offset and a scale factor in the bin information. Not sure of the use cases though. Now over to the macrology ... The besic tool to make find out about a ref or set is defined as (define-syntax-rule (mk-get-setter get-setter do-inv? AS a b c d) (define-inlinable (get-setter do-inv2? bits bits1 loop ) (lambda* (#:key (is-typed? #f) (is-scm #f) (is-fixed #f) (is-float #f) (is-integer #f) (is-single #f) (is-unsigned #f) (is-endian #f) (is-m #f) (is-inv #f)) ,,,,))) AS can be AR,AS,ARS (ref set! ref-set!) e.g depending on the type of the bin we will find a ref if AR is used, a set! if AS is used and both the ref and set for the ARS version. do-inv? can if false skip lognot stored info in the bin. get-setter is the name we define of the new setter and a b c id all of the form AR: ((1 ref-u8) (2 ref-u16)) ... AS: ((1 set-s8) (2 set-u16)) ... ARS: ((1 ref-u8 set-s8) (2 ref-u16 set-u16)) ... so a is the signed versions used, then b is the unsigned versions to use and c is teh floating operations used and finally d is the scm values used it will define an inlanable function like (define-inlinable (get-setter do-inv? bits bits1 loop) ...) So using get-setter typically means ((get-setter #f bin1 #f (lambda (set) (set v 2 val))) #:is-endian 'little ;; only consider little endian setters like I know #:is-unsigned #t ;; only use unsigned #:is-integer #t ;; only use integer representations #:is-fixed #t ;; do not use the scm value vector version= s ) So a version where we only consider handling nonegative integers of up to 64bit. The gain is faster compilation as this ideom will dispatch between 4 different versions of the the loop lambda and the compiler could inline all of them or be able to detect the one that are used and hot compile that version (a feature we do not have yet in guile) now whe you select between a ref and a set you will similarly end up with 4*4 versions =3D 16 different loop= s that. full versions is very large and a double loop with all featurs consists of (2*2 + 3*2*2*2 + 4 + 1)**2 =3D 33*33 ~ 1000 versions of the loop which is crazy if we shou= ld expand the loop for all cases in the compilation. Now guile would just use a functional approach and not expand the loop everywhere. We will have parameterised versions of libraries so that one can select which versions to compile for. for example the general functions that performs transform form one supervector to another is a general ideom that would use the full dispatc which is not practical, So for e.g. bitwise operations one could do (define-values (l-not l-and l-or -xor) (generate-bit-ops #:is-endian 'little ;; only consider little endian setters like I know #:is-unsigned #t ;; only use unsigned #:is-integer #t ;; only use integer representations #:is-fixed #t ;; do not use the scm value vector versions )) As you realise although the compiler ca innline stuff, the complexity is too big for the compiler to expand all the loops. In the end this facility should not be needed, but currently I think it=C3=A4s a good idea. That's the plan! On Thu, Sep 2, 2021 at 5:45 PM Stefan Israelsson Tampe < stefan.itampe@gmail.com> wrote: > Hi guilers! > > My next project is to explore a more advanced bytevector structure than > today's bytevectors. > I think that having this infrastructure in guile and core code taken > advantage of it like having strings otop of it and allowing our string > library to use those (the difficult case is probably to get regexps worki= ng > properly) > > Anyhow this is my initial comment in the code: > > #| > The idea of this data structure is to note that when we employ full > large datastructure scans we can allow for a much more rich and featurefu= ll > datastructure then a simple bytevector. The reason is that we can divide > the data in byte chunks and spend most of the time scanning copying mapin= g > those areas with usual methis, even optimized C - code taken advantage of > advanced cpu opcodes are possible here. ANd by dividing it in chunks we g= et > a lot of new features with essentiually no cose with more than complexity > which we manage mostly in scheme. We gain many things, > > 1. Many new features that can vary on the pages > > 2. less memory hogs as > a. it can use copy ion write semantics > b. it does not need to fins 1GB continuous blocks > > 3. potentially faster operations as we can fast foorward the zeroe on wri= te > pages compared to pure bytevectors > > 4. we can allow for swaping and refferential datastructures to speed up > copying > even further > > 5. can get better fiber features of C programs that spends seconds or > minutes on > performing an operation because it will just spend a microsecond or su= ch > in C-land and then swap back to Scheme. CTRL-C will also work nicely. > > 6. We could potentially build a string library untop of these > datastructures and > also we could add features to pages that lead to a much richer > interface. > > 7. resizing is much faster end efficient > > 8. reversing is super quick > > 9. queues and stacks of byte data can have a very efficient > implementations > > Drawback: > 1. More complex as we need to consider boudaries > 2. Slower one off operations like bytevector-u8-get as guile compiles the > core operatoins to quite effective JIT CPU encodings. But maybe we can > disign some caching to make those operations much faster and even have > suporting JIT operations. > > |# > > WDYT ? > > --000000000000b338df05cb724c88 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Today I added structure to support=C2=A0supervectors of sc= heme values and refactored the code with a nice macrology. So now we
ha= ve an infrastructure that the compiler can compile to very efficient code. = All loop must be dispatched to the type of ref and set
operations= . But the good part is that this selection is done only=C2=A0once on each b= in. which=C2=A0can be amortised with all the work on the
loop. Th= is means that there can be an explosion in the number of combinations. The = design is such that one can select the set
of variants used in a = nice interface. So let's discuss=C2=A0the setup to illustrate this poin= t afet a small detour to algebra

After investigati= ng the structure of bit like vectors today I turned to algebraic operations= and wonder about what structure we can have
regarding supervecto= rs. First to note is that storing an offset in the bin can be of value if w= e only consider=C2=A0+ and - operations so for a bin=C2=A0
with v= alues X we store it as a=C2=A0+ X, now adding (a1=C2=A0+ X1)=C2=A0+ (a2 + X= 2) lead to the final value (a1=C2=A0+ a2)=C2=A0+ (X1 + X2) which means that=
a1 and a2 can be general values and we could try to compress the= X1 and X2 to a smaller byte structure

For multipl= ication we can have a scaling operation and if we only conisder=C2=A0 * / w= e have
(b1 * X1)=C2=A0 * (b2 * X2) =3D (b1*b2) (X1*X2)
<= div>
Mixing multiplications will lead to problems but essenti= ally if you add number you can gain if the scaling is the same e.g.
(a1=C2=A0+ bX1)=C2=A0+ (a2=C2=A0+ b*X2) =3D (a1=C2=A0+ a2)=C2=A0+ b (X1= =C2=A0+ X2).=C2=A0

complexity wise one do not win = here, but the X1 and X2 could be one type of number and the scale and offse= t of a larger
type.

All operations=C2=A0= + - * /=C2=A0 of a constant bin with a fat bin can be fast if we store a sc= aling and an offset.=C2=A0

This is the basic s= tructure when considering basic algebra and one could possibly benefit by s= toring and offset and a scale
factor in the bin information. Not = sure of the use cases though.

Now over to the macr= ology ...

The besic tool to make find out about a = ref or set is defined as

(define-syntax-rule (mk-g= et-setter get-setter do-inv? AS a b c d)
=C2=A0 (define-inlinable (get-s= etter do-inv2? bits bits1 loop )
=C2=A0 =C2=A0 (lambda* (#:key (is-typed= ? #f)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-scm=C2=A0 =C2=A0 #f)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-fixed=C2=A0 =C2=A0 #f)
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-float =C2=A0#f)=C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-integer=C2=A0 #f)=C2= =A0 =C2=A0 =C2=A0 =C2=A0=C2=A0
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0(is-single #f)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-unsign= ed #f)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(is-endian #f)
=C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0(is-m =C2=A0 =C2=A0 =C2=A0#f)
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0(is-inv =C2=A0 =C2=A0#f))

,,,,)))=

AS can be AR,AS,ARS=C2=A0 =C2=A0 (ref set! ref-se= t!) e.g depending on the type of the bin we will find a ref if AR is used, = a set! if AS is used and both=C2=A0
the ref and set for the ARS v= ersion. do-inv? can if false skip lognot stored info in the bin. get-setter= is the name we define of the new setter and a b c=C2=A0 id all of the form=
AR:=C2=A0 =C2=A0((1 ref-u8) (2 ref-u16)) ...=C2=A0
AS:= =C2=A0 =C2=A0((1 set-s8) (2 set-u16)) ...=C2=A0
ARS: ((1 ref-= u8 set-s8) (2 ref-u16 set-u16)) ...=C2=A0

so a= is the signed versions used, then b is the unsigned versions to use and c = is teh floating operations used and finally d is the scm values used
<= div>
it will define an inlanable function like
(def= ine-inlinable (get-setter do-inv? bits bits1=C2=A0 loop) ...)
So using get-setter typically means
((get-setter #f b= in1 #f=C2=A0
=C2=A0 =C2=A0(lambda (set) (set v 2 val)))

=C2=A0 =C2=A0#:is-endian 'little=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 ;; only consider little endian setters like I know=C2=A0
=C2=A0 =C2=A0#:is-unsigned=C2=A0 #t=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= ;; only use unsigned
=C2=A0 =C2=A0#:is-integer=C2=A0 =C2=A0 =C2= =A0 #t=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; only use integer representations=
=C2=A0 =C2=A0#:is-fixed=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 #t=C2= =A0 =C2=A0 =C2=A0 =C2=A0 ;; do not use the scm value vector versions
<= div>)
So a version where we only consider handling nonegative int= egers of up to 64bit. The gain is faster compilation as this ideom=C2=A0wil= l dispatch
between 4 different versions=C2=A0of the the loop lamb= da and the compiler could inline all of them or be able to detect the one t= hat are used and hot compile that version
(a feature we do not ha= ve yet in guile) now whe you select between a ref and a set you will simila= rly=C2=A0end up with 4*4 versions =3D 16 different loops that. full version= s
is very large and a double loop with all featurs=C2=A0consists = of (2*2=C2=A0+ 3*2*2*2 + 4=C2=A0+ 1)**2 =3D 33*33 ~ 1000 versions of the lo= op which is crazy if we should expand the loop
for all cases in t= he compilation. Now guile would just use a functional approach and not expa= nd the loop everywhere. We will have parameterised versions of
li= braries so that one can select which versions=C2=A0to compile for. for exam= ple the general functions that performs transform form one supervector to a= nother is a general
ideom=C2=A0that would use the full dispatc=C2= =A0which is not practical,=C2=A0

So for e.g. bitwi= se operations one could do
(define-values (l-not l-and l-or -xor)= =C2=A0
=C2=A0 =C2=A0 (generate-bit-ops=C2=A0
=C2= =A0 =C2=A0 =C2=A0 =C2=A0#:is-endian 'little=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 ;; only consider little endian setters like I know=C2=A0
= =C2=A0 =C2=A0 =C2=A0 =C2=A0#:is-unsigned=C2=A0 #t=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0;; only use unsigned
=C2=A0 =C2=A0 =C2=A0 =C2=A0#:is-in= teger=C2=A0 =C2=A0 =C2=A0 #t=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0;; only use i= nteger representations
=C2=A0 =C2=A0 =C2=A0 =C2=A0#:is-fixed=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0#t=C2=A0 =C2=A0 =C2=A0 =C2=A0 ;; do not use = the scm value vector versions
=C2=A0 =C2=A0 =C2=A0))
<= div>
As you realise although the compiler ca innline stuff, t= he complexity is too big for the compiler to expand all the loops. In the e= nd this facility
should not be needed, but currently I think it= =C3=A4s a good idea.

That's the plan!















=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0



















On Thu, Sep 2, 202= 1 at 5:45 PM Stefan Israelsson Tampe <stefan.itampe@gmail.com> wrote:
Hi guilers!

My next project is to explore a more advanced bytevector structure th= an today's bytevectors.=C2=A0
I think that having this infras= tructure in guile and core code taken advantage=C2=A0of it like having stri= ngs otop of it and allowing our string library to use those (the difficult = case is probably to get regexps working properly)

= Anyhow this is my initial comment in the code:

#|<= br>The idea of this data structure is to note that when we employ full
l= arge datastructure scans we can allow for a much more rich and featurefull<= br>datastructure then a simple bytevector. The reason is that we can divide=
the data in byte chunks and spend most of the time scanning copying map= ing
those areas with usual methis, even optimized C - code taken advanta= ge of advanced cpu opcodes are possible here. ANd by dividing it in chunks = we get a lot of new features with essentiually no cose with more than compl= exity which we manage mostly in scheme. We gain many things,

1. Many= new features that can vary on the pages

2. less memory hogs as
= =C2=A0 =C2=A0a. it can use copy ion write semantics
=C2=A0 =C2=A0b. it d= oes not need to fins 1GB continuous blocks

3. potentially faster ope= rations as we can fast foorward the zeroe on write
=C2=A0 =C2=A0pages co= mpared to pure bytevectors

4. we can allow for swaping and refferent= ial datastructures to speed up copying
=C2=A0 =C2=A0even further

= 5. can get better fiber features of C programs that spends seconds or minut= es on
=C2=A0 =C2=A0performing an operation because it will just spend a = microsecond or such
=C2=A0 =C2=A0in C-land and then swap back to Scheme.= CTRL-C will also work nicely.

6. We could potentially build a strin= g library untop of these datastructures and
=C2=A0 =C2=A0also we could a= dd features to pages that lead to a much richer interface.
=C2=A0
7.= resizing is much faster end efficient

8. reversing is super quick
9. queues and stacks of byte data can have a very efficient implement= ations

Drawback:
1. More complex as we need to consider boudarie= s
2. Slower one off operations like bytevector-u8-get as guile compiles = the
=C2=A0 =C2=A0core operatoins to quite effective JIT CPU encodings. = But maybe we can
=C2=A0 =C2=A0disign some caching to make those operatio= ns much faster and even have
=C2=A0 =C2=A0suporting JIT operations.
<= br>|#

WDYT ?

--000000000000b338df05cb724c88--