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: Mon, 6 Sep 2021 04:10:50 +0200 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000002497a705cb4a2972" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="36731"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Mon Sep 06 04:11:26 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 1mN46Y-0009OA-Qy for guile-devel@m.gmane-mx.org; Mon, 06 Sep 2021 04:11:26 +0200 Original-Received: from localhost ([::1]:54056 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mN46W-00037T-UG for guile-devel@m.gmane-mx.org; Sun, 05 Sep 2021 22:11:24 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48370) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mN46D-000374-Vr for guile-devel@gnu.org; Sun, 05 Sep 2021 22:11:06 -0400 Original-Received: from mail-pf1-x434.google.com ([2607:f8b0:4864:20::434]:38567) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mN46B-0005bG-OR for guile-devel@gnu.org; Sun, 05 Sep 2021 22:11:05 -0400 Original-Received: by mail-pf1-x434.google.com with SMTP id s29so4450086pfw.5 for ; Sun, 05 Sep 2021 19:11:03 -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=h7Xd5vhtOqgNpHG/LWTyIHkx/5EgLa7EKOndnMXLI4k=; b=hluK17EMPXb2bDkP4Q9A1jjEtkKkIZZKBIwGhErkKSthDvUhMrZ7QGGVpC/9YKVme3 jzOiePTFk4MxapldOTKJPti7JMAAwv0aIcELV2g++gaJG9yHeVEMvBHVfJKnmokhy0MH 1MJi93Id/Eeuo5XtJeP4iZ4VV6IB31MzWqVF0t3oRCVVM/qVPkLcKM33d5mKr4PxM0jP Cs0V2BY0YDys7o94SUllUsjKOsJ4wjauMitHvVkCU5fRWNhLIWvMwjb/X7Osh3nB2O1l fST6KorMxLiVO4xMfGH7OegwnG997LlnhQViptTK7T6uC2zSbvJqe2/TejQUdWbnsARq Khsg== 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=h7Xd5vhtOqgNpHG/LWTyIHkx/5EgLa7EKOndnMXLI4k=; b=EclvzgQsyvNXhQjdq6TKnYh/DYzPa7LcuqS2AoBCvQZyVe1GgI2YhmxlcnFi5zc1tR 2BtnXX85B0UtnAIoPY9VhB+QXwJVOy0d5s+9kZz3gyTWux8FdzI3EVE+onloabxnynSF cKyMPurdMm4Bd1tXQKX81FGQR0H1s26MyC3evaNtCZ092KuoNSEHDQTOGLK2OFw5NUbX Fp6jhl0zqHxAFtZS7qjo9N6ehL0/6JhbUjxhxIBcSHIWGESbGtRVlvSTqonW7020ZKUD fM+JjJpW64jmP5HQdE0tcj34DZa/oe4DvIz/UztOX8s4LGO6YJqC9MVYjhQaxZFgtK+q J2YQ== X-Gm-Message-State: AOAM533l05p/AV/pBKtV2OsQWhEjO1l9uPSj4laeMGA4fFO9x2LHtiR+ bwMl1tk8lTenUvhPrT34iFkzvl6lpXgEbgv5v7+mLB/Vud4= X-Google-Smtp-Source: ABdhPJyIAFFAK63IS823ncOg3NiPxTvsJaFfEV2enKGArMVKKjBbZhRLF3GzDEZ9yCmtUsObPgxgC9iysA6XE0F1ek4= X-Received: by 2002:a63:4610:: with SMTP id t16mr10028772pga.176.1630894261834; Sun, 05 Sep 2021 19:11:01 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::434; envelope-from=stefan.itampe@gmail.com; helo=mail-pf1-x434.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:20842 Archived-At: --0000000000002497a705cb4a2972 Content-Type: text/plain; charset="UTF-8" Further developments are now in, features are (guided somewhat by how the memory in linux/unix is managed and current guile strings) 1. chunked vectors e.g. we dived the vector in areas with different properties 2. optionally typed e.g. we consider a vector of u32 etc of data so there is a notion of object length and byte length 3. unaligned data transfers can be mitigated (controlled by a depth parameter) by considering a tree e.g. the chunk is a supervector itself with the same size as the old chunk 4. growing and shrinking can be effective 5. we have a pre side and a post side so queues and stacks are well modeled by this 6. fast reverse operation (useful for queues) 7. supervectors can be read only 8. ro super vectors allow cow (copy on write) sharing 9. types can grow e.g. we can start with a u8 general layout and have some chunks in u16 and some in u32 all tree like and controlled by an allowed depth 10. we can shar data that means that a shared copy can write to the original vector it copied from 11. zero chunks 12. all in scheme, but can take advantage of superfast c-code that mayby uses some advance processor op not possible in guile etc for hot paths, the advanantage is that i) the chunks means better fibers integration with no long stalls because it repeats frequently to scheme and ii) the supervector library have an API that makes the programming experience pleasant to implement the operations. 13. good default sizes of chunks to make sure that they are large enough to amortise the overhead of the chunks 14. fast append append! 15. pretty fast indexing, lookup of a position where the speed goes from basically a vector lookup to tree lookup controlled by the level parameter 16. auto aligns supervectors chunks to allow fast operations. Next a) testing testing testing and debugging b) making a string implementation with guiles string interface that will guide some util functions for the general supervector. c) try find a regexp library that can work with chunked vectors. d) make the supervector work with ports so that we do not need to go via strings to create a large data structure and instead of the chunked one which is built by smaller moderate sized pages e) enable user defined data on chunks f) some data transfers can be much faster in C when e.g. one copy from u8 to u64 g) allow supervectors with SCM objects as elements h) allow chunked bitvectors and chunked bitvector operations i) docs like readme Project: https://gitlab.com/tampe/stis-supervectors/-/tree/main On Thu, Sep 2, 2021 at 5:54 PM Stefan Israelsson Tampe < stefan.itampe@gmail.com> wrote: > Oh I just created the project, you can follow it here: > > https://gitlab.com/tampe/stis-supervectors > > 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 working >> 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 >> featurefull >> 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 maping >> 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 get >> 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 >> write >> 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 >> such >> 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 ? >> >> --0000000000002497a705cb4a2972 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Further developments are now in, features are (guided some= what by how the memory in linux/unix is managed and current guile strings)<= div>
1.=C2=A0 =C2=A0chunked vectors e.g. we dived the vector = in areas with different properties
2.=C2=A0 =C2=A0optionally type= d e.g. we consider a vector of u32 etc of data so there is a notion of obje= ct length and byte length
3.=C2=A0 =C2=A0unaligned data transfers= =C2=A0can be mitigated (controlled by a depth parameter) by considering a t= ree e.g. the chunk is a supervector itself with the same size as the old ch= unk
4.=C2=A0 =C2=A0growing and shrinking=C2=A0can be effective
5.=C2=A0 =C2=A0we have a pre side and a post side=C2=A0 so queues a= nd stacks are well modeled by this
6.=C2=A0 =C2=A0fast reverse op= eration (useful for queues)
7.=C2=A0 =C2=A0supervectors can be re= ad only
8.=C2=A0 =C2=A0ro super vectors allow cow=C2=A0 (copy on = write) sharing
9.=C2=A0 =C2=A0types can grow e.g. we can start wi= th a u8 general layout=C2=A0and have some chunks in u16 and some in u32 all= tree like and controlled=C2=A0by an allowed=C2=A0depth
10. we ca= n shar=C2=A0data that means that a shared copy can write to the original ve= ctor it copied from
11. zero chunks
12. all in scheme, = but can take advantage of superfast c-code that mayby=C2=A0uses some advanc= e processor op not possible in guile etc for hot paths, the advanantage
=C2=A0 =C2=A0 =C2=A0 is that i) the chunks means better fibers integ= ration with no long stalls because it repeats frequently to scheme and ii) = the supervector library have an API
=C2=A0 =C2=A0 =C2=A0 that mak= es the programming experience pleasant to implement the operations.
13. good default sizes of chunks to make sure that they are large enough= to amortise the overhead of the chunks
14. fast append append!
15. pretty fast indexing, lookup of a position where the speed goe= s from basically a vector lookup to tree lookup controlled by the level par= ameter
16. auto aligns supervectors chunks to allow fast operatio= ns.

Next=C2=A0
a) testing testing testin= g and debugging
b) making a string implementation=C2=A0with guile= s string interface that will guide some util functions for the general supe= rvector.
c) try find a regexp library that can work with chunked = vectors.
d) make the supervector work with ports so that we do no= t need to go via strings to create a large data structure and instead of th= e chunked one which is built
=C2=A0 =C2=A0 =C2=A0by smaller moder= ate sized pages
e) enable user defined data on chunks
f= ) some data transfers can be much faster in C when e.g. one copy from u8 to= u64
g) allow supervectors with SCM objects as elements
h) allow chunked bitvectors=C2=A0and chunked bitvector operations
i)=C2=A0 docs like readme


Project= :



On Thu, Sep 2, 2021 at 5:54 PM Stefan Israelsson= Tampe <stefan.itampe@gmail.c= om> wrote:
Oh I just created the project, you can follow it here:

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

My next project is to explore a mor= e advanced bytevector structure than today's bytevectors.=C2=A0
I think that having this infrastructure in guile and core code taken adv= antage=C2=A0of it like having strings otop of it and allowing our string li= brary to use those (the difficult case is probably to get regexps working p= roperly)

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 featurefull
datastructure then a simple bytevector= . The reason is that we can divide
the data in byte chunks and spend mos= t of the time scanning copying maping
those areas with usual methis, eve= n optimized C - code taken advantage of advanced cpu opcodes are possible h= ere. ANd by dividing it in chunks we get a lot of new features with essenti= ually no cose with more than complexity which we manage mostly in scheme. W= e gain many things,

1. Many new features that can vary on the pages<= br>
2. less memory hogs as
=C2=A0 =C2=A0a. it can use copy ion write = semantics
=C2=A0 =C2=A0b. it does not need to fins 1GB continuous blocks=

3. potentially faster operations as we can fast foorward the zeroe = on write
=C2=A0 =C2=A0pages compared to pure bytevectors

4. we ca= n allow for swaping and refferential datastructures to speed up copying
= =C2=A0 =C2=A0even further

5. can get better fiber features of C prog= rams that spends seconds or minutes on
=C2=A0 =C2=A0performing an operat= ion because it will just spend a microsecond or such
=C2=A0 =C2=A0in C-l= and and then swap back to Scheme. CTRL-C will also work nicely.

6. W= e could potentially build a string library untop of these datastructures an= d
=C2=A0 =C2=A0also we could add features to pages that lead to a much r= icher interface.
=C2=A0
7. resizing is much faster end efficient
=
8. reversing is super quick

9. queues and stacks of byte data ca= n have a very efficient implementations

Drawback:
1. More comple= x as we need to consider boudaries
2. Slower one off operations like byt= evector-u8-get as guile compiles the
=C2=A0 =C2=A0core operatoins to qu= ite effective JIT CPU encodings. But maybe we can
=C2=A0 =C2=A0disign so= me caching to make those operations much faster and even have
=C2=A0 =C2= =A0suporting JIT operations.

|#

WDYT ?<= /div>

--0000000000002497a705cb4a2972--