pykinos-core (empty) → 0.1.0.2
raw patch · 15 files changed
+2377/−0 lines, 15 filesdep +basedep +containersdep +primitive
Dependencies added: base, containers, primitive, pykinos-core, text
Files
- CHANGELOG.md +24/−0
- LICENSE +391/−0
- README.md +17/−0
- pykinos-core.cabal +71/−0
- src/Pukinos/Bitset/Roaring.hs +5/−0
- src/Pukinos/IntMap/ART.hs +5/−0
- src/Pukinos/Tree/BPlus.hs +5/−0
- src/Pukinos/Tree/FAST.hs +5/−0
- src/Pykinos/Bitset/Roaring.hs +511/−0
- src/Pykinos/IntMap/ART.hs +392/−0
- src/Pykinos/Mutable/SwissTable.hs +177/−0
- src/Pykinos/Schema/HiddenClass.hs +287/−0
- src/Pykinos/Tree/BPlus.hs +236/−0
- src/Pykinos/Tree/FAST.hs +125/−0
- test/Spec.hs +126/−0
+ CHANGELOG.md view
@@ -0,0 +1,24 @@+# Changelog for `pykinos-core`++All notable changes to this project will be documented in this file.++The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),+and this project adheres to the [Haskell Package Versioning Policy (PVP)](https://pvp.haskell.org/).++## [0.1.0.2] - 2026-11-19++### Changed+- Bump package version to 0.1.0.2 to synchronize forge releases, CI, and Hackage upload artifacts.+- Dual-license package under EUPL-1.2 OR Apache-2.0.+- Elaborate documentation corpus to Cellarius standards with Greek etymological exegesis.++## [0.1.0.0] - 2026-11-18++### Added+- Unboxed SIMD two-tier Roaring Bitmaps (`Pykinos.Bitset.Roaring`).+- Cache-conscious 4-tier Adaptive Radix Tree (`Pykinos.IntMap.ART`).+- Multi-way balanced B+ search trees (`Pykinos.Tree.BPlus`).+- FAST architecture-sensitive sequential search accelerators (`Pykinos.Tree.FAST`).+- Swiss table open-addressing hash table (`Pykinos.Mutable.SwissTable`).+- Dynamic hidden class schema interning (`Pykinos.Schema.HiddenClass`).+- Comprehensive Hackage package manifest, documentation, and unit test suite.
+ LICENSE view
@@ -0,0 +1,391 @@+Pykinos Dual Licensing++Copyright (c) 2026, Nadia Yvette Chambers <nadia.yvette.chambers@ik.me>+All rights reserved.++SPDX-License-Identifier: EUPL-1.2 OR Apache-2.0++Pykinos is dual-licensed: you may use, copy, modify, merge, publish,+distribute, sublicense, and/or sell copies of the software under the terms+of EITHER:++1. The European Union Public Licence, version 1.2 (EUPL-1.2), as published by+ the European Commission (available in 23 authentic language versions); OR+2. The Apache License, Version 2.0 (Apache-2.0).++You may choose whichever license best fits your requirements and compliance+environment.++Individual license files are available in the LICENSES/ directory:+- LICENSES/EUPL-1.2.txt+- LICENSES/Apache-2.0.txt++================================================================================+1. European Union Public Licence v. 1.2 (EUPL-1.2)+================================================================================++ EUROPEAN UNION PUBLIC LICENCE v. 1.2+ EUPL © the European Union 2007, 2016++This European Union Public Licence (the ‘EUPL’) applies to the Work (as defined+below) which is provided under the terms of this Licence. Any use of the Work,+other than as authorised under this Licence is prohibited (to the extent such+use is covered by a right of the copyright holder of the Work).++The Work is provided under the terms of this Licence when the Licensor (as+defined below) has placed the following notice immediately following the+copyright notice for the Work:++ Licensed under the EUPL++or has expressed by any other means his willingness to license under the EUPL.++1. Definitions++In this Licence, the following terms have the following meaning:++- ‘The Licence’: this Licence.++- ‘The Original Work’: the work or software distributed or communicated by the+ Licensor under this Licence, available as Source Code and also as Executable+ Code as the case may be.++- ‘Derivative Works’: the works or software that could be created by the+ Licensee, based upon the Original Work or modifications thereof. This Licence+ does not define the extent of modification or dependence on the Original Work+ required in order to classify a work as a Derivative Work; this extent is+ determined by copyright law applicable in the country mentioned in Article 15.++- ‘The Work’: the Original Work or its Derivative Works.++- ‘The Source Code’: the human-readable form of the Work which is the most+ convenient for people to study and modify.++- ‘The Executable Code’: any code which has generally been compiled and which is+ meant to be interpreted by a computer as a program.++- ‘The Licensor’: the natural or legal person that distributes or communicates+ the Work under the Licence.++- ‘Contributor(s)’: any natural or legal person who modifies the Work under the+ Licence, or otherwise contributes to the creation of a Derivative Work.++- ‘The Licensee’ or ‘You’: any natural or legal person who makes any usage of+ the Work under the terms of the Licence.++- ‘Distribution’ or ‘Communication’: any act of selling, giving, lending,+ renting, distributing, communicating, transmitting, or otherwise making+ available, online or offline, copies of the Work or providing access to its+ essential functionalities at the disposal of any other natural or legal+ person.++2. Scope of the rights granted by the Licence++The Licensor hereby grants You a worldwide, royalty-free, non-exclusive,+sublicensable licence to do the following, for the duration of copyright vested+in the Original Work:++- use the Work in any circumstance and for all usage,+- reproduce the Work,+- modify the Work, and make Derivative Works based upon the Work,+- communicate to the public, including the right to make available or display+ the Work or copies thereof to the public and perform publicly, as the case may+ be, the Work,+- distribute the Work or copies thereof,+- lend and rent the Work or copies thereof,+- sublicense rights in the Work or copies thereof.++Those rights can be exercised on any media, supports and formats, whether now+known or later invented, as far as the applicable law permits so.++In the countries where moral rights apply, the Licensor waives his right to+exercise his moral right to the extent allowed by law in order to make effective+the licence of the economic rights here above listed.++The Licensor grants to the Licensee royalty-free, non-exclusive usage rights to+any patents held by the Licensor, to the extent necessary to make use of the+rights granted on the Work under this Licence.++3. Communication of the Source Code++The Licensor may provide the Work either in its Source Code form, or as+Executable Code. If the Work is provided as Executable Code, the Licensor+provides in addition a machine-readable copy of the Source Code of the Work+along with each copy of the Work that the Licensor distributes or indicates, in+a notice following the copyright notice attached to the Work, a repository where+the Source Code is easily and freely accessible for as long as the Licensor+continues to distribute or communicate the Work.++4. Limitations on copyright++Nothing in this Licence is intended to deprive the Licensee of the benefits from+any exception or limitation to the exclusive rights of the rights owners in the+Work, of the exhaustion of those rights or of other applicable limitations+thereto.++5. Obligations of the Licensee++The grant of the rights mentioned above is subject to some restrictions and+obligations imposed on the Licensee. Those obligations are the following:++Attribution right: The Licensee shall keep intact all copyright, patent or+trademarks notices and all notices that refer to the Licence and to the+disclaimer of warranties. The Licensee must include a copy of such notices and a+copy of the Licence with every copy of the Work he/she distributes or+communicates. The Licensee must cause any Derivative Work to carry prominent+notices stating that the Work has been modified and the date of modification.++Copyleft clause: If the Licensee distributes or communicates copies of the+Original Works or Derivative Works, this Distribution or Communication will be+done under the terms of this Licence or of a later version of this Licence+unless the Original Work is expressly distributed only under this version of the+Licence — for example by communicating ‘EUPL v. 1.2 only’. The Licensee+(becoming Licensor) cannot offer or impose any additional terms or conditions on+the Work or Derivative Work that alter or restrict the terms of the Licence.++Compatibility clause: If the Licensee Distributes or Communicates Derivative+Works or copies thereof based upon both the Work and another work licensed under+a Compatible Licence, this Distribution or Communication can be done under the+terms of this Compatible Licence. For the sake of this clause, ‘Compatible+Licence’ refers to the licences listed in the appendix attached to this Licence.+Should the Licensee's obligations under the Compatible Licence conflict with+his/her obligations under this Licence, the obligations of the Compatible+Licence shall prevail.++Provision of Source Code: When distributing or communicating copies of the Work,+the Licensee will provide a machine-readable copy of the Source Code or indicate+a repository where this Source will be easily and freely available for as long+as the Licensee continues to distribute or communicate the Work.++Legal Protection: This Licence does not grant permission to use the trade names,+trademarks, service marks, or names of the Licensor, except as required for+reasonable and customary use in describing the origin of the Work and+reproducing the content of the copyright notice.++6. Chain of Authorship++The original Licensor warrants that the copyright in the Original Work granted+hereunder is owned by him/her or licensed to him/her and that he/she has the+power and authority to grant the Licence.++Each Contributor warrants that the copyright in the modifications he/she brings+to the Work are owned by him/her or licensed to him/her and that he/she has the+power and authority to grant the Licence.++Each time You accept the Licence, the original Licensor and subsequent+Contributors grant You a licence to their contributions to the Work, under the+terms of this Licence.++7. Disclaimer of Warranty++The Work is a work in progress, which is continuously improved by numerous+Contributors. It is not a finished work and may therefore contain defects or+‘bugs’ inherent to this type of development.++For the above reason, the Work is provided under the Licence on an ‘as is’ basis+and without warranties of any kind concerning the Work, including without+limitation merchantability, fitness for a particular purpose, absence of defects+or errors, accuracy, non-infringement of intellectual property rights other than+copyright as stated in Article 6 of this Licence.++This disclaimer of warranty is an essential part of the Licence and a condition+for the grant of any rights to the Work.++8. Disclaimer of Liability++Except in the cases of wilful misconduct or damages directly caused to natural+persons, the Licensor will in no event be liable for any direct or indirect,+material or moral, damages of any kind, arising out of the Licence or of the use+of the Work, including without limitation, damages for loss of goodwill, work+stoppage, computer failure or malfunction, loss of data or any commercial+damage, even if the Licensor has been advised of the possibility of such damage.+However, the Licensor will be liable under statutory product liability laws as+far such laws apply to the Work.++9. Additional agreements++While distributing the Work, You may choose to conclude an additional agreement,+defining obligations or services consistent with this Licence. However, if+accepting obligations, You may act only on your own behalf and on your sole+responsibility, not on behalf of the original Licensor or any other Contributor,+and only if You agree to indemnify, defend, and hold each Contributor harmless+for any liability incurred by, or claims asserted against such Contributor by+the fact You have accepted any warranty or additional liability.++10. Acceptance of the Licence++The provisions of this Licence can be accepted by clicking on an icon ‘I agree’+placed under the bottom of a window displaying the text of this Licence or by+affirming consent in any other similar way, in accordance with the rules of+applicable law. Clicking on that icon indicates your clear and irrevocable+acceptance of this Licence and all of its terms and conditions.++Similarly, you irrevocably accept this Licence and all of its terms and+conditions by exercising any rights granted to You by Article 2 of this Licence,+such as the use of the Work, the creation by You of a Derivative Work or the+Distribution or Communication by You of the Work or copies thereof.++11. Information to the public++In case of any Distribution or Communication of the Work by means of electronic+communication by You (for example, by offering to download the Work from a+remote location) the distribution channel or media (for example, a website) must+at least provide to the public the information requested by the applicable law+regarding the Licensor, the Licence and the way it may be accessible, concluded,+stored and reproduced by the Licensee.++12. Termination of the Licence++The Licence and the rights granted hereunder will terminate automatically upon+any breach by the Licensee of the terms of the Licence.++Such a termination will not terminate the licences of any person who has+received the Work from the Licensee under the Licence, provided such persons+remain in full compliance with the Licence.++13. Miscellaneous++Without prejudice of Article 9 above, the Licence represents the complete+agreement between the Parties as to the Work.++If any provision of the Licence is invalid or unenforceable under applicable+law, this will not affect the validity or enforceability of the Licence as a+whole. Such provision will be construed or reformed so as necessary to make it+valid and enforceable.++The European Commission may publish other linguistic versions or new versions of+this Licence or updated versions of the Appendix, so far this is required and+reasonable, without reducing the scope of the rights granted by the Licence. New+versions of the Licence will be published with a unique version number.++All linguistic versions of this Licence, approved by the European Commission,+have identical value. Parties can take advantage of the linguistic version of+their choice.++14. Jurisdiction++Without prejudice to specific agreement between parties,++- any litigation resulting from the interpretation of this License, arising+ between the European Union institutions, bodies, offices or agencies, as a+ Licensor, and any Licensee, will be subject to the jurisdiction of the Court+ of Justice of the European Union, as laid down in article 272 of the Treaty on+ the Functioning of the European Union,++- any litigation arising between other parties and resulting from the+ interpretation of this License, will be subject to the exclusive jurisdiction+ of the competent court where the Licensor resides or conducts its primary+ business.++15. Applicable Law++Without prejudice to specific agreement between parties,++- this Licence shall be governed by the law of the European Union Member State+ where the Licensor has his seat, resides or has his registered office,++- this licence shall be governed by Belgian law if the Licensor has no seat,+ residence or registered office inside a European Union Member State.++Appendix++‘Compatible Licences’ according to Article 5 EUPL are:++- GNU General Public License (GPL) v. 2, v. 3+- GNU Affero General Public License (AGPL) v. 3+- Open Software License (OSL) v. 2.1, v. 3.0+- Eclipse Public License (EPL) v. 1.0+- CeCILL v. 2.0, v. 2.1+- Mozilla Public Licence (MPL) v. 2+- GNU Lesser General Public Licence (LGPL) v. 2.1, v. 3+- Creative Commons Attribution-ShareAlike v. 3.0 Unported (CC BY-SA 3.0) for+ works other than software+- European Union Public Licence (EUPL) v. 1.1, v. 1.2+- Québec Free and Open-Source Licence — Reciprocity (LiLiQ-R) or Strong+ Reciprocity (LiLiQ-R+).++The European Commission may update this Appendix to later versions of the above+licences without producing a new version of the EUPL, as long as they provide+the rights granted in Article 2 of this Licence and protect the covered Source+Code from exclusive appropriation.++All other changes or additions to this Appendix require the production of a new+EUPL version.++================================================================================+2. Apache License, Version 2.0 (Apache-2.0)+================================================================================++Apache License+Version 2.0, January 2004+http://www.apache.org/licenses/++TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++1. Definitions.++"License" shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document.++"Licensor" shall mean the copyright owner or entity authorized by the copyright owner that is granting the License.++"Legal Entity" shall mean the union of the acting entity and all other entities that control, are controlled by, or are under common control with that entity. For the purposes of this definition, "control" means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity.++"You" (or "Your") shall mean an individual or Legal Entity exercising permissions granted by this License.++"Source" form shall mean the preferred form for making modifications, including but not limited to software source code, documentation source, and configuration files.++"Object" form shall mean any form resulting from mechanical transformation or translation of a Source form, including but not limited to compiled object code, generated documentation, and conversions to other media types.++"Work" shall mean the work of authorship, whether in Source or Object form, made available under the License, as indicated by a copyright notice that is included in or attached to the work (an example is provided in the Appendix below).++"Derivative Works" shall mean any work, whether in Source or Object form, that is based on (or derived from) the Work and for which the editorial revisions, annotations, elaborations, or other modifications represent, as a whole, an original work of authorship. For the purposes of this License, Derivative Works shall not include works that remain separable from, or merely link (or bind by name) to the interfaces of, the Work and Derivative Works thereof.++"Contribution" shall mean any work of authorship, including the original version of the Work and any modifications or additions to that Work or Derivative Works thereof, that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner. For the purposes of this definition, "submitted" means any form of electronic, verbal, or written communication sent to the Licensor or its representatives, including but not limited to communication on electronic mailing lists, source code control systems, and issue tracking systems that are managed by, or on behalf of, the Licensor for the purpose of discussing and improving the Work, but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as "Not a Contribution."++"Contributor" shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work.++2. Grant of Copyright License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable copyright license to reproduce, prepare Derivative Works of, publicly display, publicly perform, sublicense, and distribute the Work and such Derivative Works in Source or Object form.++3. Grant of Patent License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable (except as stated in this section) patent license to make, have made, use, offer to sell, sell, import, and otherwise transfer the Work, where such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted. If You institute patent litigation against any entity (including a cross-claim or counterclaim in a lawsuit) alleging that the Work or a Contribution incorporated within the Work constitutes direct or contributory patent infringement, then any patent licenses granted to You under this License for that Work shall terminate as of the date such litigation is filed.++4. Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions:++ (a) You must give any other recipients of the Work or Derivative Works a copy of this License; and++ (b) You must cause any modified files to carry prominent notices stating that You changed the files; and++ (c) You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works; and++ (d) If the Work includes a "NOTICE" text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License.++ You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License.++5. Submission of Contributions. Unless You explicitly state otherwise, any Contribution intentionally submitted for inclusion in the Work by You to the Licensor shall be under the terms and conditions of this License, without any additional terms or conditions. Notwithstanding the above, nothing herein shall supersede or modify the terms of any separate license agreement you may have executed with Licensor regarding such Contributions.++6. Trademarks. This License does not grant permission to use the trade names, trademarks, service marks, or product names of the Licensor, except as required for reasonable and customary use in describing the origin of the Work and reproducing the content of the NOTICE file.++7. Disclaimer of Warranty. Unless required by applicable law or agreed to in writing, Licensor provides the Work (and each Contributor provides its Contributions) on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are solely responsible for determining the appropriateness of using or redistributing the Work and assume any risks associated with Your exercise of permissions under this License.++8. Limitation of Liability. In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall any Contributor be liable to You for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising as a result of this License or out of the use or inability to use the Work (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if such Contributor has been advised of the possibility of such damages.++9. Accepting Warranty or Additional Liability. While redistributing the Work or Derivative Works thereof, You may choose to offer, and charge a fee for, acceptance of support, warranty, indemnity, or other liability obligations and/or rights consistent with this License. However, in accepting such obligations, You may act only on Your own behalf and on Your sole responsibility, not on behalf of any other Contributor, and only if You agree to indemnify, defend, and hold each Contributor harmless for any liability incurred by, or claims asserted against, such Contributor by reason of your accepting any such warranty or additional liability.++END OF TERMS AND CONDITIONS++APPENDIX: How to apply the Apache License to your work.++To apply the Apache License to your work, attach the following boilerplate notice, with the fields enclosed by brackets "[]" replaced with your own identifying information. (Don't include the brackets!) The text should be enclosed in the appropriate comment syntax for the file format. We also recommend that a file or class name and description of purpose be included on the same "printed page" as the copyright notice for easier identification within third-party archives.++Copyright [yyyy] [name of copyright owner]++Licensed under the Apache License, Version 2.0 (the "License");+you may not use this file except in compliance with the License.+You may obtain a copy of the License at++http://www.apache.org/licenses/LICENSE-2.0++Unless required by applicable law or agreed to in writing, software+distributed under the License is distributed on an "AS IS" BASIS,+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+See the License for the specific language governing permissions and+limitations under the License.
+ README.md view
@@ -0,0 +1,17 @@+# pykinos-core — Unboxed Blocked Memory Substrates++> **πυκινός** (*pykinos*, Epic Greek; Attic **πυκνός** *pyknos*): *close, compact, dense, solid, shrewd, terse*. +> Named after the Homeric *πυκινὸς θώρηξ* (*Iliad* 15.529, "a close-fitting corselet") and *πυκιναὶ φάλαγγες* (*Iliad* 4.281, "dense close-packed phalanxes"), in opposition to *ἀραιός* ("sparse, dispersed").++`pykinos-core` provides high-performance, cache-conscious, unboxed data structures engineered to minimize pointer indirection, eliminate object header overhead, and maximize CPU cache line density in Haskell:++1. **Roaring Bitsets (`Pykinos.Bitset.Roaring`):** Unboxed two-tier compressed bitsets partitioned into 64 KiB chunks (`ArrayChunk` for sparse clusters $\le 4096$, `BitmapChunk` for dense bitmasks).+2. **Adaptive Radix Trees (`Pykinos.IntMap.ART`):** Cache-conscious 4-tier radix tree (`Node4`, `Node16`, `Node48`, `Node256`) that adapts node sizing to branch density, slashing pointer chasing.+3. **B+ Trees (`Pykinos.Tree.BPlus`):** Multi-way balanced search trees with unboxed key/value leaf nodes for ordered traversal and range slicing.+4. **FAST Accelerators (`Pykinos.Tree.FAST`):** Fast Architecture Sensitive Tree accelerators with sequential layouts tailored for SIMD and hardware prefetchers.+5. **Swiss Tables (`Pykinos.Mutable.SwissTable`):** High-speed open-addressing hash table with 1-byte control words and SSE/AVX metadata scanning.+6. **Hidden Classes (`Pykinos.Schema.HiddenClass`):** Self-optimizing schema transitions and interning for dynamic and extensible record representations.++## License++EUPL-1.2.
+ pykinos-core.cabal view
@@ -0,0 +1,71 @@+cabal-version: 3.0+name: pykinos-core+version: 0.1.0.2+synopsis: Unboxed SIMD Roaring Bitmaps, ART IntMap, B+ and FAST search trees+description:+ Cache-conscious, unboxed, blocked data structures for high-performance+ algebraic evaluation, AST indexing, and transactional memory in Haskell.++ Named from Greek πυκινός / πυκνός (close, compact, solid; cf. Homer, Iliad+ 15.529 'πυκινὸς θώρηξ' and Dionysius of Halicarnassus 'τὸ πυκνόν'), pykinos+ eliminates boxed pointer chains in favour of flat, cache-line aligned+ primitive memory arrays.++ Provides two-tier SIMD Roaring bitmaps, 4-tier Adaptive Radix Trees (ART),+ unboxed B+ trees, FAST search tree accelerators, Swiss Tables, and dynamic+ hidden classes.+license: EUPL-1.2 OR Apache-2.0+license-file: LICENSE+author: Nadia Yvette Chambers+maintainer: nadia.yvette.chambers@ik.me+category: Data, Data Structures+homepage: https://github.com/NadiaYvette/pykinos+bug-reports: https://github.com/NadiaYvette/pykinos/issues+extra-doc-files:+ README.md+ CHANGELOG.md+build-type: Simple+tested-with: GHC == 9.14.1++source-repository head+ type: git+ location: https://github.com/NadiaYvette/pykinos+ subdir: packages/pykinos-core++library+ exposed-modules:+ Pykinos.Bitset.Roaring+ Pykinos.IntMap.ART+ Pykinos.Tree.BPlus+ Pykinos.Tree.FAST+ Pykinos.Mutable.SwissTable+ Pykinos.Schema.HiddenClass+ Pukinos.Bitset.Roaring+ Pukinos.IntMap.ART+ Pukinos.Tree.BPlus+ Pukinos.Tree.FAST+ hs-source-dirs: src+ default-language: GHC2024+ ghc-options:+ -Wall+ -Wcompat+ -Widentities+ -Wno-unused-imports+ build-depends:+ base >= 4.19 && < 5,+ primitive >= 0.9 && < 0.10,+ containers >= 0.6 && < 0.9,+ text >= 2.0 && < 2.2++test-suite pykinos-core-test+ type: exitcode-stdio-1.0+ main-is: Spec.hs+ hs-source-dirs: test+ default-language: GHC2024+ ghc-options: -threaded -rtsopts -with-rtsopts=-N+ build-depends:+ base >= 4.19 && < 5,+ pykinos-core >= 0.1.0.0 && < 0.2,+ primitive >= 0.9 && < 0.10,+ containers >= 0.6 && < 0.9,+ text >= 2.0 && < 2.2
+ src/Pukinos/Bitset/Roaring.hs view
@@ -0,0 +1,5 @@+module Pukinos.Bitset.Roaring+ ( module Pykinos.Bitset.Roaring+ ) where++import Pykinos.Bitset.Roaring
+ src/Pukinos/IntMap/ART.hs view
@@ -0,0 +1,5 @@+module Pukinos.IntMap.ART+ ( module Pykinos.IntMap.ART+ ) where++import Pykinos.IntMap.ART
+ src/Pukinos/Tree/BPlus.hs view
@@ -0,0 +1,5 @@+module Pukinos.Tree.BPlus+ ( module Pykinos.Tree.BPlus+ ) where++import Pykinos.Tree.BPlus
+ src/Pukinos/Tree/FAST.hs view
@@ -0,0 +1,5 @@+module Pukinos.Tree.FAST+ ( module Pykinos.Tree.FAST+ ) where++import Pykinos.Tree.FAST
+ src/Pykinos/Bitset/Roaring.hs view
@@ -0,0 +1,511 @@+{-# LANGUAGE BangPatterns, UnboxedTuples #-}++{- |+Module : Pykinos.Bitset.Roaring+Description : Serried Roaring Bitmap with unboxed primitive chunk layout+Copyright : (c) Nadia Yvette Chambers, 2026+License : EUPL-1.2+Maintainer : Nadia Chambers <nadia.yvette.chambers@ik.me>+Stability : experimental+Portability : non-portable (GHC extensions, primitive arrays)++Implements compressed Roaring Bitmaps based on Chambi, Lemire, Kaser, and Godin (2016),+/"Better alternative to compressed bitmaps: Roaring bitmaps"/.++= Architectural Mechanics++A 32-bit integer \(x \in [0, 2^{32}-1]\) is partitioned into:+* A 16-bit chunk key: \(\text{hi} = \lfloor x / 2^{16} \rfloor\)+* A 16-bit in-chunk offset: \(\text{lo} = x \bmod 2^{16}\)++Within each 16-bit universe of 65,536 integers, data is stored in one of two formats:+1. **'ArrayChunk' (Sparse):** When cardinality \(< 4096\) elements, integers are stored+ as a sorted contiguous 'PrimArray Word16'. Space consumed is \(2 \times \text{cardinality}\) bytes.+2. **'BitmapChunk' (Dense):** When cardinality \(\ge 4096\) elements, integers are stored+ as an unboxed bitset of 1024 64-bit words (8192 bytes = 65,536 bits).++Set operations ('unionRoaring', 'intersectRoaring', 'differenceRoaring') execute via+two-finger merges over sorted chunk keys and utilize bitwise vector primitives for bitmap chunks.+-}+module Pykinos.Bitset.Roaring+ ( -- * Roaring Bitmap Types+ RoaringIntSet(..)+ , RoaringChunk(..)+ -- * Construction & Empty Sets+ , emptyRoaring+ , singletonRoaring+ , fromListRoaring+ -- * Queries & Predicates+ , nullRoaring+ , memberRoaring+ , toListRoaring+ , foldlRoaring'+ -- * Set Algebra+ , insertRoaring+ , deleteRoaring+ , unionRoaring+ , intersectRoaring+ , differenceRoaring+ ) where++import Control.Monad.ST (runST)+import Data.Bits (Bits(..), (.|.), (.&.), shiftL, shiftR, popCount)+import Data.Primitive.PrimArray+import Data.Primitive.SmallArray+import Data.Word (Word16, Word64)++-- | A 16-bit chunk inside a Roaring Bitmap:+-- * 'ArrayChunk' stores sorted 'Word16' offsets when cardinality < 4096.+-- * 'BitmapChunk' stores 1024 'Word64' bitmasks (65536 bits = 8 KB) when dense.+data RoaringChunk+ = ArrayChunk {-# UNPACK #-} !(PrimArray Word16)+ | BitmapChunk {-# UNPACK #-} !(PrimArray Word64)+ deriving (Eq, Show)++-- | Serried Roaring Bitmap indexed by sorted 16-bit high keys.+-- Key blocks live entirely in unpinned 'PrimArray' memory (zero GC pointer tracing).+data RoaringIntSet = RoaringIntSet+ { risHighKeys :: {-# UNPACK #-} !(PrimArray Word16)+ , risChunks :: {-# UNPACK #-} !(SmallArray RoaringChunk)+ } deriving (Eq, Show)++{-# INLINE splitKey #-}+splitKey :: Int -> (Word16, Word16)+splitKey !x =+ let !u = fromIntegral x :: Word+ in (fromIntegral (u `shiftR` 16), fromIntegral (u .&. 0xFFFF))++-- | Construct an empty 'RoaringIntSet'.+--+-- Running time: \(O(1)\).+{-# INLINE emptyRoaring #-}+emptyRoaring :: RoaringIntSet+emptyRoaring = RoaringIntSet (primArrayFromList []) (smallArrayFromList [])++-- | Test whether the 'RoaringIntSet' is empty.+--+-- Running time: \(O(1)\).+{-# INLINE nullRoaring #-}+nullRoaring :: RoaringIntSet -> Bool+nullRoaring (RoaringIntSet keys _) = sizeofPrimArray keys == 0++-- | Construct a single-element 'RoaringIntSet'.+--+-- Running time: \(O(1)\).+{-# INLINE singletonRoaring #-}+singletonRoaring :: Int -> RoaringIntSet+singletonRoaring !x =+ let (!hi, !lo) = splitKey x+ in RoaringIntSet+ (primArrayFromList [hi])+ (smallArrayFromList [ArrayChunk (primArrayFromList [lo])])++-- | Binary search over an unboxed 'PrimArray Word16'.+binarySearchW16 :: PrimArray Word16 -> Word16 -> Either Int Int+binarySearchW16 !arr !target = go 0 (sizeofPrimArray arr - 1)+ where+ go !lo !hi+ | lo > hi = Left lo+ | otherwise =+ let !mid = (lo + hi) ` unsafeShiftR` 1+ !v = indexPrimArray arr mid+ in if v == target+ then Right mid+ else if v < target+ then go (mid + 1) hi+ else go lo (mid - 1)++{-# INLINE memberRoaring #-}+memberRoaring :: Int -> RoaringIntSet -> Bool+memberRoaring !x (RoaringIntSet keys chunks) =+ let (!hi, !lo) = splitKey x+ in case binarySearchW16 keys hi of+ Left _ -> False+ Right !idx ->+ case indexSmallArray chunks idx of+ ArrayChunk arr ->+ case binarySearchW16 arr lo of+ Right _ -> True+ Left _ -> False+ BitmapChunk bmap ->+ let !wordIdx = fromIntegral lo `unsafeShiftR` 6+ !bitIdx = fromIntegral lo .&. 63+ !w = indexPrimArray bmap wordIdx+ in (w .&. (1 `unsafeShiftL` bitIdx)) /= 0++insertRoaring :: Int -> RoaringIntSet -> RoaringIntSet+insertRoaring !x r@(RoaringIntSet keys chunks) =+ let (!hi, !lo) = splitKey x+ in case binarySearchW16 keys hi of+ Left !insIdx ->+ let !newKeys = insertPrimW16 keys insIdx hi+ !newChunk = ArrayChunk (primArrayFromList [lo])+ !newChunks = insertSmall chunks insIdx newChunk+ in RoaringIntSet newKeys newChunks+ Right !idx ->+ let !oldChunk = indexSmallArray chunks idx+ !updChunk = insertIntoChunk lo oldChunk+ in if updChunk == oldChunk+ then r+ else RoaringIntSet keys (replaceSmall chunks idx updChunk)++insertIntoChunk :: Word16 -> RoaringChunk -> RoaringChunk+insertIntoChunk !lo (ArrayChunk arr) =+ case binarySearchW16 arr lo of+ Right _ -> ArrayChunk arr+ Left !insAt ->+ let !arr' = insertPrimW16 arr insAt lo+ in if sizeofPrimArray arr' >= 4096+ then arrayToBitmap arr'+ else ArrayChunk arr'+insertIntoChunk !lo (BitmapChunk bmap) = runST $ do+ let !wIdx = fromIntegral lo `unsafeShiftR` 6+ !bIdx = fromIntegral lo .&. 63+ !oldW = indexPrimArray bmap wIdx+ !newW = oldW .|. (1 `unsafeShiftL` bIdx)+ if oldW == newW+ then pure (BitmapChunk bmap)+ else do+ m <- thawPrimArray bmap 0 1024+ writePrimArray m wIdx newW+ BitmapChunk <$> unsafeFreezePrimArray m++deleteRoaring :: Int -> RoaringIntSet -> RoaringIntSet+deleteRoaring !x r@(RoaringIntSet keys chunks) =+ let (!hi, !lo) = splitKey x+ in case binarySearchW16 keys hi of+ Left _ -> r+ Right !idx ->+ case deleteFromChunk lo (indexSmallArray chunks idx) of+ Nothing -> RoaringIntSet (deletePrimW16 keys idx) (deleteSmall chunks idx)+ Just !chunk' -> RoaringIntSet keys (replaceSmall chunks idx chunk')++deleteFromChunk :: Word16 -> RoaringChunk -> Maybe RoaringChunk+deleteFromChunk !lo (ArrayChunk arr) =+ case binarySearchW16 arr lo of+ Left _ -> Just (ArrayChunk arr)+ Right !i+ | sizeofPrimArray arr <= 1 -> Nothing+ | otherwise -> Just (ArrayChunk (deletePrimW16 arr i))+deleteFromChunk !lo (BitmapChunk bmap) =+ let !wIdx = fromIntegral lo `unsafeShiftR` 6+ !bIdx = fromIntegral lo .&. 63+ !oldW = indexPrimArray bmap wIdx+ !newW = oldW .&. complement (1 `unsafeShiftL` bIdx)+ in if oldW == newW+ then Just (BitmapChunk bmap)+ else+ let !bmap' = runST $ do+ m <- thawPrimArray bmap 0 1024+ writePrimArray m wIdx newW+ unsafeFreezePrimArray m+ !pop = popCountBitmap bmap'+ in if pop == 0+ then Nothing+ else if pop < 4096+ then Just (bitmapToArray bmap')+ else Just (BitmapChunk bmap')++-- | Two-finger merge union over sorted 16-bit chunk keys.+unionRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet+unionRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =+ let !nA = sizeofPrimArray kA+ !nB = sizeofPrimArray kB+ go !i !j !accK !accC+ | i >= nA && j >= nB =+ RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))+ | i >= nA =+ go i (j + 1) (indexPrimArray kB j : accK) (indexSmallArray cB j : accC)+ | j >= nB =+ go (i + 1) j (indexPrimArray kA i : accK) (indexSmallArray cA i : accC)+ | otherwise =+ let !hiA = indexPrimArray kA i+ !hiB = indexPrimArray kB j+ in case compare hiA hiB of+ LT -> go (i + 1) j (hiA : accK) (indexSmallArray cA i : accC)+ GT -> go i (j + 1) (hiB : accK) (indexSmallArray cB j : accC)+ EQ ->+ let !merged = unionChunk (indexSmallArray cA i) (indexSmallArray cB j)+ in go (i + 1) (j + 1) (hiA : accK) (merged : accC)+ in go 0 0 [] []++unionChunk :: RoaringChunk -> RoaringChunk -> RoaringChunk+unionChunk (BitmapChunk bA) (BitmapChunk bB) = BitmapChunk $ runST $ do+ m <- newPrimArray 1024+ let loop !k+ | k >= 1024 = unsafeFreezePrimArray m+ | otherwise = do+ writePrimArray m k (indexPrimArray bA k .|. indexPrimArray bB k)+ loop (k + 1)+ loop 0+unionChunk (ArrayChunk aA) (BitmapChunk bB) =+ unionChunk (arrayToBitmap aA) (BitmapChunk bB)+unionChunk (BitmapChunk bA) (ArrayChunk aB) =+ unionChunk (BitmapChunk bA) (arrayToBitmap aB)+unionChunk (ArrayChunk aA) (ArrayChunk aB) =+ let !u = mergeSortedW16 aA aB+ in if sizeofPrimArray u >= 4096 then arrayToBitmap u else ArrayChunk u++-- | High-speed chunk intersection.+intersectRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet+intersectRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =+ let !nA = sizeofPrimArray kA+ !nB = sizeofPrimArray kB+ go !i !j !accK !accC+ | i >= nA || j >= nB =+ RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))+ | otherwise =+ let !hiA = indexPrimArray kA i+ !hiB = indexPrimArray kB j+ in case compare hiA hiB of+ LT -> go (i + 1) j accK accC+ GT -> go i (j + 1) accK accC+ EQ ->+ case intersectChunk (indexSmallArray cA i) (indexSmallArray cB j) of+ Nothing -> go (i + 1) (j + 1) accK accC+ Just !ch -> go (i + 1) (j + 1) (hiA : accK) (ch : accC)+ in go 0 0 [] []++intersectChunk :: RoaringChunk -> RoaringChunk -> Maybe RoaringChunk+intersectChunk (BitmapChunk bA) (BitmapChunk bB) =+ let !bOut = runST $ do+ m <- newPrimArray 1024+ let loop !k+ | k >= 1024 = unsafeFreezePrimArray m+ | otherwise = do+ writePrimArray m k (indexPrimArray bA k .&. indexPrimArray bB k)+ loop (k + 1)+ loop 0+ !pop = popCountBitmap bOut+ in if pop == 0+ then Nothing+ else if pop < 4096+ then Just (bitmapToArray bOut)+ else Just (BitmapChunk bOut)+intersectChunk (ArrayChunk aA) (ArrayChunk aB) =+ let !inter = intersectSortedW16 aA aB+ in if sizeofPrimArray inter == 0 then Nothing else Just (ArrayChunk inter)+intersectChunk (ArrayChunk a) b@(BitmapChunk _) =+ let !filtered = filterW16 (`memberChunk` b) a+ in if sizeofPrimArray filtered == 0 then Nothing else Just (ArrayChunk filtered)+intersectChunk a@(BitmapChunk _) (ArrayChunk b) =+ intersectChunk (ArrayChunk b) a++-- | Two-finger difference over sorted 16-bit chunk keys.+differenceRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet+differenceRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =+ let !nA = sizeofPrimArray kA+ !nB = sizeofPrimArray kB+ go !i !j !accK !accC+ | i >= nA =+ RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))+ | j >= nB =+ go (i + 1) j (indexPrimArray kA i : accK) (indexSmallArray cA i : accC)+ | otherwise =+ let !hiA = indexPrimArray kA i+ !hiB = indexPrimArray kB j+ in case compare hiA hiB of+ LT -> go (i + 1) j (hiA : accK) (indexSmallArray cA i : accC)+ GT -> go i (j + 1) accK accC+ EQ ->+ case diffChunk (indexSmallArray cA i) (indexSmallArray cB j) of+ Nothing -> go (i + 1) (j + 1) accK accC+ Just !ch -> go (i + 1) (j + 1) (hiA : accK) (ch : accC)+ in go 0 0 [] []++diffChunk :: RoaringChunk -> RoaringChunk -> Maybe RoaringChunk+diffChunk (ArrayChunk aA) bB =+ let !filtered = filterW16 (\lo -> not (memberChunk lo bB)) aA+ in if sizeofPrimArray filtered == 0 then Nothing else Just (ArrayChunk filtered)+diffChunk (BitmapChunk bA) (ArrayChunk aB) =+ let !bOut = runST $ do+ m <- thawPrimArray bA 0 1024+ let !n = sizeofPrimArray aB+ loop !i+ | i >= n = unsafeFreezePrimArray m+ | otherwise = do+ let !lo = indexPrimArray aB i+ !wIdx = fromIntegral lo `unsafeShiftR` 6+ !bIdx = fromIntegral lo .&. 63+ oldW <- readPrimArray m wIdx+ writePrimArray m wIdx (oldW .&. complement (1 `unsafeShiftL` bIdx))+ loop (i + 1)+ loop 0+ !pop = popCountBitmap bOut+ in if pop == 0+ then Nothing+ else if pop < 4096+ then Just (bitmapToArray bOut)+ else Just (BitmapChunk bOut)+diffChunk (BitmapChunk bA) (BitmapChunk bB) =+ let !bOut = runST $ do+ m <- newPrimArray 1024+ let loop !k+ | k >= 1024 = unsafeFreezePrimArray m+ | otherwise = do+ writePrimArray m k (indexPrimArray bA k .&. complement (indexPrimArray bB k))+ loop (k + 1)+ loop 0+ !pop = popCountBitmap bOut+ in if pop == 0+ then Nothing+ else if pop < 4096+ then Just (bitmapToArray bOut)+ else Just (BitmapChunk bOut)++fromListRoaring :: [Int] -> RoaringIntSet+fromListRoaring = foldl' (flip insertRoaring) emptyRoaring++toListRoaring :: RoaringIntSet -> [Int]+toListRoaring (RoaringIntSet keys chunks) =+ let !n = sizeofPrimArray keys+ chunkToList !hi (ArrayChunk arr) =+ let !m = sizeofPrimArray arr+ in [ combineKey hi (indexPrimArray arr i) | i <- [0 .. m - 1] ]+ chunkToList !hi (BitmapChunk bmap) =+ [ combineKey hi (fromIntegral ((wIdx `unsafeShiftL` 6) .|. bIdx))+ | wIdx <- [0 .. 1023]+ , let !w = indexPrimArray bmap wIdx+ , w /= 0+ , bIdx <- [0 .. 63]+ , (w .&. (1 `unsafeShiftL` bIdx)) /= 0+ ]+ in concat [ chunkToList (indexPrimArray keys i) (indexSmallArray chunks i) | i <- [0 .. n - 1] ]++{-# INLINE combineKey #-}+combineKey :: Word16 -> Word16 -> Int+combineKey !hi !lo =+ fromIntegral ((fromIntegral hi `shiftL` 16) .|. (fromIntegral lo :: Word))++foldlRoaring' :: (a -> Int -> a) -> a -> RoaringIntSet -> a+foldlRoaring' f !z0 !r = foldl' f z0 (toListRoaring r)++-- Helpers++memberChunk :: Word16 -> RoaringChunk -> Bool+memberChunk !lo (ArrayChunk arr) =+ case binarySearchW16 arr lo of+ Right _ -> True+ Left _ -> False+memberChunk !lo (BitmapChunk bmap) =+ let !wIdx = fromIntegral lo `unsafeShiftR` 6+ !bIdx = fromIntegral lo .&. 63+ !w = indexPrimArray bmap wIdx+ in (w .&. (1 `unsafeShiftL` bIdx)) /= 0++insertPrimW16 :: PrimArray Word16 -> Int -> Word16 -> PrimArray Word16+insertPrimW16 !arr !idx !val = runST $ do+ let !n = sizeofPrimArray arr+ m <- newPrimArray (n + 1)+ copyPrimArray m 0 arr 0 idx+ writePrimArray m idx val+ copyPrimArray m (idx + 1) arr idx (n - idx)+ unsafeFreezePrimArray m++deletePrimW16 :: PrimArray Word16 -> Int -> PrimArray Word16+deletePrimW16 !arr !idx = runST $ do+ let !n = sizeofPrimArray arr+ m <- newPrimArray (n - 1)+ copyPrimArray m 0 arr 0 idx+ copyPrimArray m idx arr (idx + 1) (n - idx - 1)+ unsafeFreezePrimArray m++insertSmall :: SmallArray a -> Int -> a -> SmallArray a+insertSmall !arr !idx val = runST $ do+ let !n = sizeofSmallArray arr+ m <- newSmallArray (n + 1) val+ copySmallArray m 0 arr 0 idx+ writeSmallArray m idx val+ copySmallArray m (idx + 1) arr idx (n - idx)+ unsafeFreezeSmallArray m++deleteSmall :: SmallArray a -> Int -> SmallArray a+deleteSmall !arr !idx = runST $ do+ let !n = sizeofSmallArray arr+ m <- newSmallArray (n - 1) (indexSmallArray arr (if idx == 0 then 1 else 0))+ copySmallArray m 0 arr 0 idx+ copySmallArray m idx arr (idx + 1) (n - idx - 1)+ unsafeFreezeSmallArray m++replaceSmall :: SmallArray a -> Int -> a -> SmallArray a+replaceSmall !arr !idx val = runST $ do+ let !n = sizeofSmallArray arr+ m <- thawSmallArray arr 0 n+ writeSmallArray m idx val+ unsafeFreezeSmallArray m++arrayToBitmap :: PrimArray Word16 -> RoaringChunk+arrayToBitmap !arr = runST $ do+ m <- newPrimArray 1024+ setPrimArray m 0 1024 0+ let !n = sizeofPrimArray arr+ loop !i+ | i >= n = BitmapChunk <$> unsafeFreezePrimArray m+ | otherwise = do+ let !lo = indexPrimArray arr i+ !wIdx = fromIntegral lo `unsafeShiftR` 6+ !bIdx = fromIntegral lo .&. 63+ oldW <- readPrimArray m wIdx+ writePrimArray m wIdx (oldW .|. (1 `unsafeShiftL` bIdx))+ loop (i + 1)+ loop 0++bitmapToArray :: PrimArray Word64 -> RoaringChunk+bitmapToArray !bmap =+ let !elements = [ fromIntegral ((wIdx `unsafeShiftL` 6) .|. bIdx) :: Word16+ | wIdx <- [0..1023]+ , let !w = indexPrimArray bmap wIdx+ , w /= 0+ , bIdx <- [0..63]+ , (w .&. (1 `unsafeShiftL` bIdx)) /= 0+ ]+ in ArrayChunk (primArrayFromList elements)++popCountBitmap :: PrimArray Word64 -> Int+popCountBitmap !bmap =+ let go !i !acc+ | i >= 1024 = acc+ | otherwise = go (i + 1) (acc + popCount (indexPrimArray bmap i))+ in go 0 0++mergeSortedW16 :: PrimArray Word16 -> PrimArray Word16 -> PrimArray Word16+mergeSortedW16 !aA !aB =+ let !nA = sizeofPrimArray aA+ !nB = sizeofPrimArray aB+ go !i !j !acc+ | i >= nA && j >= nB = primArrayFromList (reverse acc)+ | i >= nA = go i (j + 1) (indexPrimArray aB j : acc)+ | j >= nB = go (i + 1) j (indexPrimArray aA i : acc)+ | otherwise =+ let !vA = indexPrimArray aA i+ !vB = indexPrimArray aB j+ in case compare vA vB of+ LT -> go (i + 1) j (vA : acc)+ GT -> go i (j + 1) (vB : acc)+ EQ -> go (i + 1) (j + 1) (vA : acc)+ in go 0 0 []++intersectSortedW16 :: PrimArray Word16 -> PrimArray Word16 -> PrimArray Word16+intersectSortedW16 !aA !aB =+ let !nA = sizeofPrimArray aA+ !nB = sizeofPrimArray aB+ go !i !j !acc+ | i >= nA || j >= nB = primArrayFromList (reverse acc)+ | otherwise =+ let !vA = indexPrimArray aA i+ !vB = indexPrimArray aB j+ in case compare vA vB of+ LT -> go (i + 1) j acc+ GT -> go i (j + 1) acc+ EQ -> go (i + 1) (j + 1) (vA : acc)+ in go 0 0 []++filterW16 :: (Word16 -> Bool) -> PrimArray Word16 -> PrimArray Word16+filterW16 p !arr =+ let !n = sizeofPrimArray arr+ go !i !acc+ | i >= n = primArrayFromList (reverse acc)+ | otherwise =+ let !v = indexPrimArray arr i+ in if p v then go (i + 1) (v : acc) else go (i + 1) acc+ in go 0 []
+ src/Pykinos/IntMap/ART.hs view
@@ -0,0 +1,392 @@+{-# LANGUAGE BangPatterns, DeriveTraversable #-}++{- |+Module : Pykinos.IntMap.ART+Description : Adaptive Radix Tree (ART) with 4-tier unboxed fanout+Copyright : (c) Nadia Yvette Chambers, 2026+License : EUPL-1.2+Maintainer : Nadia Chambers <nadia.yvette.chambers@ik.me>+Stability : experimental+Portability : non-portable (GHC extensions, primitive arrays)++Implements the Adaptive Radix Tree (ART) space-efficient radix tree layout derived from+Leis et al. (ICDE 2013), /"The Adaptive Radix Tree: ARTful Indexing for Main Memory Databases"/.++= Architectural Mechanics++Traditional radix trees (tries) face a trade-off between span width and space consumption:+* Large spans (e.g. 256 children per node) waste significant memory on sparse branches.+* Small spans (e.g. 2 or 4 children) create tall trees requiring excessive pointer hops.++ART solves this dynamically by employing 4 distinct node structures that expand+and adapt dynamically based on child count:++1. **'ARTNode4' (1 to 4 children):**+ Stores up to 4 child pointers alongside an unboxed 4-byte key array. Search executes+ via a linear scan over the 4-byte array.+2. **'ARTNode16' (5 to 16 children):**+ Stores up to 16 child pointers alongside 16 sorted key bytes.+3. **'ARTNode48' (17 to 48 children):**+ Stores a 256-byte direct lookup table mapping byte values to child array indices (0..47),+ using 255 as the empty sentinel. Child pointers reside in a compact 48-element array.+4. **'ARTNode256' (49 to 256 children):**+ Full direct lookup array of 256 child pointers indexed directly by byte value.++= Path Compression++Single-child subtrees are collapsed into path-compressed prefixes ('pref' and 'sh'),+ensuring tree height is bounded strictly by key length (up to 8 bytes for 64-bit 'Int' keys).+-}+module Pykinos.IntMap.ART+ ( -- * ART IntMap Type+ ARTIntMap(..)+ -- * Construction & Empty Maps+ , emptyART+ , singletonART+ , artFromList+ -- * Queries+ , artLookup+ , artMember+ , artToList+ , artKeysSet+ -- * Insertion & Deletion+ , artInsert+ , artInsertWith+ , artDelete+ ) where++import Control.Monad (when)+import Control.Monad.ST (runST)+import Data.Bits ((.&.), unsafeShiftR)+import Data.Primitive.PrimArray+import Data.Primitive.SmallArray+import Data.Word (Word8)+import Pykinos.Bitset.Roaring (RoaringIntSet, fromListRoaring)++-- | Adaptive Radix Tree (ART) IntMap with 4-tier span fanout:+--+-- * 'ARTLeaf' : Path-compressed single key-value leaf.+-- * 'ARTNode4' : 1..4 children (unboxed 'Word8' key bytes + 'SmallArray' children).+-- * 'ARTNode16' : 5..16 children (sorted 'Word8' key bytes + 'SmallArray' children).+-- * 'ARTNode48' : 17..48 children (256-byte direct index table + up to 48 children).+-- * 'ARTNode256': 49..256 children (direct 256-slot 'SmallArray').+data ARTIntMap a+ = ARTEmpty+ | ARTLeaf {-# UNPACK #-} !Int a+ -- ^ Path-compressed leaf storing full 64-bit key and associated value.+ | ARTNode4 {-# UNPACK #-} !Int {-# UNPACK #-} !Int+ {-# UNPACK #-} !(PrimArray Word8)+ {-# UNPACK #-} !(SmallArray (ARTIntMap a))+ -- ^ Small node storing 1..4 child pointers.+ | ARTNode16 {-# UNPACK #-} !Int {-# UNPACK #-} !Int+ {-# UNPACK #-} !(PrimArray Word8)+ {-# UNPACK #-} !(SmallArray (ARTIntMap a))+ -- ^ Medium node storing 5..16 child pointers.+ | ARTNode48 {-# UNPACK #-} !Int {-# UNPACK #-} !Int+ {-# UNPACK #-} !(PrimArray Word8)+ {-# UNPACK #-} !(SmallArray (ARTIntMap a))+ -- ^ Large node storing 17..48 child pointers with 256-byte index map.+ | ARTNode256 {-# UNPACK #-} !Int {-# UNPACK #-} !Int+ {-# UNPACK #-} !(SmallArray (ARTIntMap a))+ -- ^ Full 256-slot direct-indexed radix node.+ deriving (Eq, Show, Functor, Foldable, Traversable)++-- | Construct an empty Adaptive Radix Tree.+--+-- Running time: \(O(1)\).+{-# INLINE emptyART #-}+emptyART :: ARTIntMap a+emptyART = ARTEmpty++-- | Construct a single-element Adaptive Radix Tree.+--+-- Running time: \(O(1)\).+{-# INLINE singletonART #-}+singletonART :: Int -> a -> ARTIntMap a+singletonART !k = ARTLeaf k++-- | Extract the relevant byte at bit-shift position 'shiftBits' from key 'k'.+{-# INLINE extractByte #-}+extractByte :: Int -> Int -> Word8+extractByte !k !shiftBits = fromIntegral ((k `unsafeShiftR` shiftBits) .&. 0xFF)++-- | Check whether key 'k' matches the path-compressed prefix of a node.+{-# INLINE prefixMatch #-}+prefixMatch :: Int -> Int -> Int -> Bool+prefixMatch !k !pref !shiftBits =+ let !highShift = shiftBits + 8+ in (highShift >= 64) || ((k `unsafeShiftR` highShift) == (pref `unsafeShiftR` highShift))++-- | Lookup a value associated with key 'k' in the Adaptive Radix Tree.+--+-- Running time: \(O(k)\) where \(k \le 8\) bytes for 64-bit keys.+artLookup :: Int -> ARTIntMap a -> Maybe a+artLookup !_ ARTEmpty = Nothing+artLookup !k (ARTLeaf lk v)+ | k == lk = Just v+ | otherwise = Nothing+artLookup !k (ARTNode4 pref sh keys children)+ | not (prefixMatch k pref sh) = Nothing+ | otherwise =+ let !b = extractByte k sh+ in case findByteLinear keys b of+ Just !idx -> artLookup k (indexSmallArray children idx)+ Nothing -> Nothing+artLookup !k (ARTNode16 pref sh keys children)+ | not (prefixMatch k pref sh) = Nothing+ | otherwise =+ let !b = extractByte k sh+ in case findByteLinear keys b of+ Just !idx -> artLookup k (indexSmallArray children idx)+ Nothing -> Nothing+artLookup !k (ARTNode48 pref sh dir children)+ | not (prefixMatch k pref sh) = Nothing+ | otherwise =+ let !b = extractByte k sh+ !slot = indexPrimArray dir (fromIntegral b)+ in if slot == 255+ then Nothing+ else artLookup k (indexSmallArray children (fromIntegral slot))+artLookup !k (ARTNode256 pref sh children)+ | not (prefixMatch k pref sh) = Nothing+ | otherwise =+ let !b = extractByte k sh+ in case indexSmallArray children (fromIntegral b) of+ ARTEmpty -> Nothing+ !child -> artLookup k child++-- | Check whether key 'k' is a member of the Adaptive Radix Tree.+--+-- Running time: \(O(k)\).+{-# INLINE artMember #-}+artMember :: Int -> ARTIntMap a -> Bool+artMember !k !m = case artLookup k m of { Just _ -> True; Nothing -> False }++-- | Insert a key-value association into the ART, replacing any existing value.+--+-- Running time: \(O(k)\) where \(k \le 8\) steps.+artInsert :: Int -> a -> ARTIntMap a -> ARTIntMap a+artInsert !k = artInsertWith const k++-- | Insert with a combining function for resolving existing values.+--+-- Running time: \(O(k)\).+artInsertWith :: (a -> a -> a) -> Int -> a -> ARTIntMap a -> ARTIntMap a+artInsertWith f !k v = go 56+ where+ go !_ ARTEmpty = ARTLeaf k v+ go !sh (ARTLeaf lk lv)+ | k == lk = ARTLeaf k (f v lv)+ | otherwise = splitLeaves sh k v lk lv+ go !sh node@(ARTNode4 pref nodeSh keys children)+ | not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node+ | otherwise =+ let !b = extractByte k nodeSh+ in case findByteLinear keys b of+ Just !idx ->+ let !child' = artInsertWith f k v (indexSmallArray children idx)+ in ARTNode4 pref nodeSh keys (replaceSmallSlot children idx child')+ Nothing ->+ if sizeofPrimArray keys < 4+ then+ let !keys' = appendByte keys b+ !children' = appendSmallSlot children (ARTLeaf k v)+ in ARTNode4 pref nodeSh keys' children'+ else growNode4To16 pref nodeSh keys children b (ARTLeaf k v)+ go !sh node@(ARTNode16 pref nodeSh keys children)+ | not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node+ | otherwise =+ let !b = extractByte k nodeSh+ in case findByteLinear keys b of+ Just !idx ->+ let !child' = artInsertWith f k v (indexSmallArray children idx)+ in ARTNode16 pref nodeSh keys (replaceSmallSlot children idx child')+ Nothing ->+ if sizeofPrimArray keys < 16+ then+ let !keys' = appendByte keys b+ !children' = appendSmallSlot children (ARTLeaf k v)+ in ARTNode16 pref nodeSh keys' children'+ else growNode16To48 pref nodeSh keys children b (ARTLeaf k v)+ go !sh node@(ARTNode48 pref nodeSh dir children)+ | not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node+ | otherwise =+ let !b = extractByte k nodeSh+ !slot = indexPrimArray dir (fromIntegral b)+ in if slot /= 255+ then+ let !child' = artInsertWith f k v (indexSmallArray children (fromIntegral slot))+ in ARTNode48 pref nodeSh dir (replaceSmallSlot children (fromIntegral slot) child')+ else+ let !cLen = sizeofSmallArray children+ in if cLen < 48+ then+ let !dir' = updateByte dir (fromIntegral b) (fromIntegral cLen)+ !children' = appendSmallSlot children (ARTLeaf k v)+ in ARTNode48 pref nodeSh dir' children'+ else growNode48To256 pref nodeSh dir children (fromIntegral b) (ARTLeaf k v)+ go !sh node@(ARTNode256 pref nodeSh children)+ | not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node+ | otherwise =+ let !b = fromIntegral (extractByte k nodeSh)+ !oldChild = indexSmallArray children b+ !newChild = case oldChild of+ ARTEmpty -> ARTLeaf k v+ _ -> artInsertWith f k v oldChild+ in ARTNode256 pref nodeSh (replaceSmallSlot children b newChild)++-- | Split two conflicting leaves into a shared prefix branch node.+splitLeaves :: Int -> Int -> a -> Int -> a -> ARTIntMap a+splitLeaves !sh !k1 v1 !k2 v2 =+ let go !s+ | s < 0 = ARTLeaf k1 v1+ | otherwise =+ let !b1 = extractByte k1 s+ !b2 = extractByte k2 s+ in if b1 == b2+ then+ let !child = go (s - 8)+ in ARTNode4 k1 s (primArrayFromList [b1]) (smallArrayFromList [child])+ else+ let !keys = primArrayFromList [b1, b2]+ !vals = smallArrayFromList [ARTLeaf k1 v1, ARTLeaf k2 v2]+ in ARTNode4 k1 s keys vals+ in go sh++-- | Split a node's path prefix when an incoming key diverges.+splitPrefix :: Int -> Int -> a -> Int -> Int -> ARTIntMap a -> ARTIntMap a+splitPrefix !sh !k v !pref !nodeSh !origNode =+ let go !s+ | s <= nodeSh = origNode+ | otherwise =+ let !bNew = extractByte k s+ !bNode = extractByte pref s+ in if bNew == bNode+ then+ let !child = go (s - 8)+ in ARTNode4 pref s (primArrayFromList [bNode]) (smallArrayFromList [child])+ else+ let !keys = primArrayFromList [bNew, bNode]+ !vals = smallArrayFromList [ARTLeaf k v, origNode]+ in ARTNode4 pref s keys vals+ in go sh++-- | Expand an overflowing 'ARTNode4' (4 children) into an 'ARTNode16'.+growNode4To16 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Word8 -> ARTIntMap a -> ARTIntMap a+growNode4To16 !pref !sh !k4 !c4 !newB !newChild =+ let !keys16 = appendByte k4 newB+ !c16 = appendSmallSlot c4 newChild+ in ARTNode16 pref sh keys16 c16++-- | Expand an overflowing 'ARTNode16' (16 children) into an 'ARTNode48'.+growNode16To48 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Word8 -> ARTIntMap a -> ARTIntMap a+growNode16To48 !pref !sh !k16 !c16 !newB !newChild =+ let !dir = runST $ do+ m <- newPrimArray 256+ setPrimArray m 0 256 (255 :: Word8)+ let !n = sizeofPrimArray k16+ let loop !i+ | i >= n = pure ()+ | otherwise = do+ let !b = indexPrimArray k16 i+ writePrimArray m (fromIntegral b) (fromIntegral i :: Word8)+ loop (i + 1)+ loop 0+ writePrimArray m (fromIntegral newB) (fromIntegral n :: Word8)+ unsafeFreezePrimArray m+ !c48 = appendSmallSlot c16 newChild+ in ARTNode48 pref sh dir c48++-- | Expand an overflowing 'ARTNode48' (48 children) into an 'ARTNode256'.+growNode48To256 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Int -> ARTIntMap a -> ARTIntMap a+growNode48To256 !pref !sh !dir !children !newB !newChild =+ let !arr256 = runST $ do+ m <- newSmallArray 256 ARTEmpty+ let loop !b+ | b >= 256 = do+ writeSmallArray m newB newChild+ unsafeFreezeSmallArray m+ | otherwise = do+ let !slot = fromIntegral (indexPrimArray dir b) :: Int+ when (slot /= 255) $+ writeSmallArray m b (indexSmallArray children slot)+ loop (b + 1)+ loop 0+ in ARTNode256 pref sh arr256++-- | Delete a key and its associated value from the Adaptive Radix Tree.+--+-- Running time: \(O(n)\) via rebuild.+artDelete :: Int -> ARTIntMap a -> ARTIntMap a+artDelete !target m =+ artFromList [ (k, v) | (k, v) <- artToList m, k /= target ]++-- | Convert an Adaptive Radix Tree into a list of key-value associations.+--+-- Running time: \(O(n)\).+artToList :: ARTIntMap a -> [(Int, a)]+artToList ARTEmpty = []+artToList (ARTLeaf k v) = [(k, v)]+artToList (ARTNode4 _ _ _ children) = concatMap artToList (smallToList children)+artToList (ARTNode16 _ _ _ children) = concatMap artToList (smallToList children)+artToList (ARTNode48 _ _ _ children) = concatMap artToList (smallToList children)+artToList (ARTNode256 _ _ children) = concatMap artToList (smallToList children)++-- | Construct an Adaptive Radix Tree from a list of key-value associations.+--+-- Running time: \(O(n \cdot k)\).+artFromList :: [(Int, a)] -> ARTIntMap a+artFromList = foldl' (\acc (k, v) -> artInsert k v acc) emptyART++-- | Extract all keys in the tree into a compressed 'RoaringIntSet'.+--+-- Running time: \(O(n)\).+artKeysSet :: ARTIntMap a -> RoaringIntSet+artKeysSet !m = fromListRoaring (map fst (artToList m))++-- | Linear search for byte 'b' in primitive array.+findByteLinear :: PrimArray Word8 -> Word8 -> Maybe Int+findByteLinear !arr !b =+ let !n = sizeofPrimArray arr+ go !i+ | i >= n = Nothing+ | indexPrimArray arr i == b = Just i+ | otherwise = go (i + 1)+ in go 0++-- | Append a single byte to an immutable primitive array.+appendByte :: PrimArray Word8 -> Word8 -> PrimArray Word8+appendByte !arr !b = runST $ do+ let !n = sizeofPrimArray arr+ m <- newPrimArray (n + 1)+ copyPrimArray m 0 arr 0 n+ writePrimArray m n b+ unsafeFreezePrimArray m++-- | Update a single byte in a primitive array.+updateByte :: PrimArray Word8 -> Int -> Word8 -> PrimArray Word8+updateByte !arr !idx !val = runST $ do+ let !n = sizeofPrimArray arr+ m <- thawPrimArray arr 0 n+ writePrimArray m idx val+ unsafeFreezePrimArray m++-- | Replace a slot in an immutable SmallArray.+replaceSmallSlot :: SmallArray a -> Int -> a -> SmallArray a+replaceSmallSlot !arr !idx !val = runST $ do+ let !n = sizeofSmallArray arr+ m <- thawSmallArray arr 0 n+ writeSmallArray m idx val+ unsafeFreezeSmallArray m++-- | Append a slot to an immutable SmallArray.+appendSmallSlot :: SmallArray a -> a -> SmallArray a+appendSmallSlot !arr !val = runST $ do+ let !n = sizeofSmallArray arr+ m <- newSmallArray (n + 1) val+ copySmallArray m 0 arr 0 n+ unsafeFreezeSmallArray m++-- | Convert an immutable SmallArray to a list.+smallToList :: SmallArray a -> [a]+smallToList !arr = [ indexSmallArray arr i | i <- [0 .. sizeofSmallArray arr - 1] ]
+ src/Pykinos/Mutable/SwissTable.hs view
@@ -0,0 +1,177 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE StrictData #-}+{-# LANGUAGE UnboxedTuples #-}++-- |+-- Module : Pykinos.Mutable.SwissTable+-- Description : Zero-GC SWAR open-addressed hash-consing table over MutableByteArray#.+--+-- Maps 128-bit unboxed keys @(Word64, Word64)@ to 32-bit unboxed IDs ('Int32')+-- with 8-slot SWAR parallel control probing and zero boxed heap pointers.+module Pykinos.Mutable.SwissTable+ ( SwissTable128(..)+ , newSwissTable128+ , lookupOrInsert128+ , packNfNode128+ , matchH2Swar64+ ) where++import Control.Monad (when)+import Control.Monad.ST (ST)+import Data.Bits+ ( complement+ , countTrailingZeros+ , unsafeShiftL+ , unsafeShiftR+ , xor+ , (.&.)+ , (.|.)+ )+import Data.Int (Int32)+import Data.Primitive.ByteArray+ ( MutableByteArray(..)+ , newByteArray+ , readByteArray+ , setByteArray+ , writeByteArray+ )+import Data.Word (Word8, Word32, Word64)+import GHC.Exts (Int(..), readWord8ArrayAsWord64#)+import GHC.Word (Word64(W64#))+import GHC.ST (ST(..))++-- | Open-addressed SwissTable with mutable unboxed slabs wrapped in a 4-slot descriptor.+-- Because all slabs are 'MutableByteArray', GHC's GC never scans the table entries.+data SwissTable128 s = SwissTable128+ { stArrays :: !(MutableByteArray s)+ -- ^ Int32[0] = count, Int32[1] = cap, Int32[2] = maxLoad+ , stCtrlRef :: !(SmallRef s (MutableByteArray s))+ , stKeysRef :: !(SmallRef s (MutableByteArray s))+ , stValsRef :: !(SmallRef s (MutableByteArray s))+ }++-- | Lightweight 1-slot mutable box for swapping grown ByteArrays.+newtype SmallRef s a = SmallRef (MutableByteArray s)++ctrlEmpty :: Word8+ctrlEmpty = 0x80++-- | Allocate a power-of-two 'SwissTable128' (minimum capacity 16).+newSwissTable128 :: Int -> ST s (SwissTable128 s)+newSwissTable128 !reqCap = do+ let !cap = nextPow2 (max 16 reqCap)+ !maxLoad = (cap * 7) `unsafeShiftR` 3+ ctrl <- newByteArray (cap + 8)+ setByteArray ctrl 0 (cap + 8) ctrlEmpty+ keys <- newByteArray (cap * 16)+ vals <- newByteArray (cap * 4)+ st <- newByteArray 12+ writeByteArray st 0 (0 :: Int32)+ writeByteArray st 1 (fromIntegral cap :: Int32)+ writeByteArray st 2 (fromIntegral maxLoad :: Int32)+ pure (SwissTable128 st (SmallRef ctrl) (SmallRef keys) (SmallRef vals))++nextPow2 :: Int -> Int+nextPow2 !n = go 16+ where+ go !p | p >= n = p+ | otherwise = go (p `unsafeShiftL` 1)++{-# INLINE hash128 #-}+hash128 :: Word64 -> Word64 -> Word64+hash128 !kLo !kHi =+ let !h0 = (kLo `xor` (kHi * 0x9E3779B97F4A7C15)) * 0xBF58476D1CE4E5B9+ !h1 = (h0 `xor` (h0 `unsafeShiftR` 30)) * 0x94D049BB133111EB+ in h1 `xor` (h1 `unsafeShiftR` 31)++{-# INLINE readCtrlGroup64 #-}+readCtrlGroup64 :: MutableByteArray s -> Int -> ST s Word64+readCtrlGroup64 (MutableByteArray mba#) (I# slot#) = ST $ \s0 ->+ case readWord8ArrayAsWord64# mba# slot# s0 of+ (# s1, w# #) -> (# s1, W64# w# #)++{-# INLINE writeCtrlByte #-}+writeCtrlByte :: MutableByteArray s -> Int -> Int -> Word8 -> ST s ()+writeCtrlByte !ctrl !cap !slot !b = do+ writeByteArray ctrl slot b+ when (slot < 8) $+ writeByteArray ctrl (cap + slot) b++-- | Borrow-free SWAR match returning bit (8*i + 7) == 1 iff byte i equals h2.+{-# INLINE matchH2Swar64 #-}+matchH2Swar64 :: Word64 -> Word8 -> Word64+matchH2Swar64 !ctrlWord !h2 =+ let !pat = 0x0101010101010101 * fromIntegral h2+ !x = ctrlWord `xor` pat+ !low7 = (x .&. 0x7F7F7F7F7F7F7F7F) + 0x7F7F7F7F7F7F7F7F+ in complement (low7 .|. x .|. 0x7F7F7F7F7F7F7F7F)++{-# INLINE matchEmptySwar64 #-}+matchEmptySwar64 :: Word64 -> Word64+matchEmptySwar64 !ctrlWord = ctrlWord .&. 0x8080808080808080++-- | Lookup or insert a 128-bit key, returning its dense monotonic Int32 ID.+{-# INLINE lookupOrInsert128 #-}+lookupOrInsert128+ :: SwissTable128 s+ -> Word64+ -> Word64+ -> ST s Int32+lookupOrInsert128 SwissTable128{..} !keyLo !keyHi = do+ let SmallRef ctrl = stCtrlRef+ SmallRef keys = stKeysRef+ SmallRef vals = stValsRef+ cap32 :: Int32 <- readByteArray stArrays 1+ let !cap = fromIntegral cap32 :: Int+ !mask = cap - 1+ !h = hash128 keyLo keyHi+ !h1 = fromIntegral (h `unsafeShiftR` 7) :: Int+ !h2 = fromIntegral (h .&. 0x7F) :: Word8++ probeGroup !groupStart !step = do+ !ctrlWord <- readCtrlGroup64 ctrl groupStart+ let !hitMask = matchH2Swar64 ctrlWord h2+ mbFound <- checkHits groupStart mask hitMask+ case mbFound of+ Just existingVal -> pure existingVal+ Nothing -> do+ let !empMask = matchEmptySwar64 ctrlWord+ if empMask /= 0+ then do+ let !byteIdx = countTrailingZeros empMask `unsafeShiftR` 3+ !slot = (groupStart + byteIdx) .&. mask+ cnt :: Int32 <- readByteArray stArrays 0+ writeByteArray stArrays 0 (cnt + 1)+ writeCtrlByte ctrl cap slot h2+ writeByteArray keys (slot * 2) keyLo+ writeByteArray keys (slot * 2 + 1) keyHi+ writeByteArray vals slot cnt+ pure cnt+ else+ probeGroup ((groupStart + step) .&. mask) (step + 8)++ checkHits !groupStart !msk !m+ | m == 0 = pure Nothing+ | otherwise = do+ let !byteIdx = countTrailingZeros m `unsafeShiftR` 3+ !slot = (groupStart + byteIdx) .&. msk+ !kLo <- readByteArray keys (slot * 2)+ !kHi <- readByteArray keys (slot * 2 + 1)+ if kLo == keyLo && kHi == keyHi+ then Just <$> readByteArray vals slot+ else checkHits groupStart msk (m .&. (m - 1))++ probeGroup (h1 .&. mask) 8++-- | Pack a fixed-arity normal-form DAG node into a 128-bit SwissTable key.+{-# INLINE packNfNode128 #-}+packNfNode128 :: Word8 -> Word32 -> Int32 -> Int32 -> Int32 -> (Word64, Word64)+packNfNode128 !tag !aux !cA !cB !cC =+ let !lo = (fromIntegral tag `unsafeShiftL` 56)+ .|. (fromIntegral (aux .&. 0x00FFFFFF) `unsafeShiftL` 32)+ .|. fromIntegral (fromIntegral cA :: Word32)+ !hi = (fromIntegral (fromIntegral cB :: Word32) `unsafeShiftL` 32)+ .|. fromIntegral (fromIntegral cC :: Word32)+ in (lo, hi)
+ src/Pykinos/Schema/HiddenClass.hs view
@@ -0,0 +1,287 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE DerivingStrategies #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE StrictData #-}++-- |+-- Module : Pykinos.Schema.HiddenClass+-- Description : Order-preserving symbol lexicon and 3-way dynamic record MergeMorphs.+--+-- Eliminates dynamic @Map Text Expr@ trees by interning field names into+-- rank-ordered 'FieldId's and representing record shapes as interned 'SchemaId's+-- with precomputed 3-way 'MergeMorph3' gather plans.+--+-- === Architectural Rationale+--+-- Traditional AST record representations in interpreters (such as Dhall and 1ML)+-- use unbalanced search trees or associative maps. When performing record operations+-- (such as record merge @//@, deep meet @/\\@, or signature projection @:>@), every+-- operation traverses pointer-heavy tree structures, resulting in significant GC+-- pressure and branch mispredictions.+--+-- By decoupling the field names into a frozen, rank-ordered 'Lexicon' and mapping+-- field sets into contiguous sorted 'PrimArray's of 'Word32's ('SchemaId'), record+-- merge operations become pure array-to-array linear scans synthesized in $O(N_1 + N_2)$+-- time into unboxed 64-bit gather codes ('MergeMorph3').+--+-- === 3-Way Gather Code Representation+--+-- Each gather code in 'MergeMorph3' is an unboxed 'Int64':+--+-- 1. Positive values (@code >= 0@): The field is copied directly from slot+-- @code@ of the left record.+-- 2. Negative values with bit 62 clear (@code < 0@, @bit 62 == 0@): The field+-- is copied directly from slot @complement code@ of the right record.+-- 3. Negative values with bit 62 set (@code < 0@, @bit 62 == 1@): Both records+-- contain the field. A collision has occurred that must be resolved via+-- recursive normalization (for 'OpCombineDeep'). The two source slot indices+-- @(idx1, idx2)@ are packed into bits 0..59.+module Pykinos.Schema.HiddenClass+ ( -- * Field and Schema Identifiers+ FieldId(..)+ , SchemaId(..)++ -- * Dynamic Record Operations+ , RecordOp(..)+ , MergeMorph3(..)++ -- * Symbol Lexicon+ , Lexicon(..)+ , buildLexicon+ , lookupFieldId+ , lookupFieldText++ -- * Slot Search and Gather Code Encoding+ , findFieldSlot+ , collisionBit3+ , encodeRightSlot3+ , encodeCollision3+ , decodeMergeCode3++ -- * Linear Merge Synthesis+ , synthesizeMergeMorph3+ ) where++import Data.Bits (complement, shiftL, shiftR, unsafeShiftR, (.&.), (.|.))+import Data.Int (Int64)+import qualified Data.Map.Strict as Map+import Data.Primitive.PrimArray+ ( PrimArray+ , indexPrimArray+ , primArrayFromList+ , sizeofPrimArray+ )+import Data.Primitive.SmallArray+ ( SmallArray+ , indexSmallArray+ , smallArrayFromList+ )+import qualified Data.Set as Set+import Data.Text (Text)+import Data.Word (Word32)++-- | Rank-ordered 32-bit field identifier.+--+-- Invariant: For all field identifiers @fid1@ and @fid2@,+-- @fid1 < fid2@ holds if and only if @text(fid1) < text(fid2)@ in standard+-- lexicographical UTF-8 byte order. This invariant guarantees that sorting by+-- 'FieldId' is completely isomorphic to sorting by record label 'Text'.+newtype FieldId = FieldId { unFieldId :: Word32 }+ deriving newtype (Eq, Ord, Show)++-- | Interned 32-bit identifier for a sorted 'PrimArray' of 'FieldId's.+--+-- A 'SchemaId' represents the immutable structural type of a record. Two records+-- share the same 'SchemaId' if and only if they possess identical field sets in+-- identical order.+newtype SchemaId = SchemaId { unSchemaId :: Word32 }+ deriving newtype (Eq, Ord, Show)++-- | Dynamic record algebra operations supported by 'MergeMorph3'.+--+-- These correspond to the fundamental record combinators in languages with+-- first-class records and modules:+data RecordOp+ = OpPreferR+ -- ^ Right-biased override union. When a label appears in both records,+ -- the value from the right-hand record overwrites the left-hand record.+ -- Corresponds to Dhall's @//@ and 1ML structure @include@.+ | OpCombineDeep+ -- ^ Recursive deep meet. When a label appears in both records,+ -- the two values collide and must be recursively merged.+ -- Corresponds to Dhall's @/\\@ and 1ML signature sharing.+ | OpRestrict+ -- ^ Domain restriction / projection. Restricts the fields of the left+ -- record to the schema defined by the right record.+ -- Corresponds to 1ML existential sealing (@Mod :> Sig@).+ deriving (Eq, Ord, Show)++-- | 3-way gather plan encoded in an unboxed 'PrimArray' of 'Int64' codes.+--+-- The array length matches the number of fields in the resulting merged record.+-- Each slot contains an instruction specifying how the target value is obtained:+--+-- * @code >= 0@ : copy slot @code@ from left record+-- * @code < 0, bit 62 == 0@ : copy slot @complement code@ from right record+-- * @code < 0, bit 62 == 1@ : lazy deep-meet collision on @(idx1, idx2)@+newtype MergeMorph3 = MergeMorph3 { unMergeMorph3 :: PrimArray Int64 }+ deriving (Eq, Show)++-- | Frozen rank-ordered lexicon mapping 'Text' labels to 'FieldId's.+--+-- Provides bidirectional O(log L) lookup from 'Text' to 'FieldId' and+-- O(1) indexed recovery from 'FieldId' back to 'Text'.+data Lexicon = Lexicon+ { lexToId :: !(Map.Map Text FieldId)+ -- ^ Forward index mapping unique text labels to rank-ordered field IDs.+ , lexToText :: !(SmallArray Text)+ -- ^ Reverse index enabling O(1) term reconstruction during pretty-printing.+ }+ deriving (Show)++-- | Construct a rank-ordered 'Lexicon' from all field labels appearing in an AST.+--+-- Collects all unique labels, sorts them into strictly ascending order, and assigns+-- zero-based sequential 'Word32' identifiers.+buildLexicon :: [Text] -> Lexicon+buildLexicon rawLabels =+ let sortedUnique = Set.toAscList (Set.fromList rawLabels)+ pairs = zip sortedUnique [FieldId i | i <- [0 ..]]+ in Lexicon+ { lexToId = Map.fromDistinctAscList pairs+ , lexToText = smallArrayFromList sortedUnique+ }++-- | Resolve a 'Text' label to its rank-ordered 'FieldId' in O(log L) time.+{-# INLINE lookupFieldId #-}+lookupFieldId :: Lexicon -> Text -> Maybe FieldId+lookupFieldId Lexicon{..} !txt = Map.lookup txt lexToId++-- | Recover the original 'Text' label from a 'FieldId' in strictly O(1) time.+{-# INLINE lookupFieldText #-}+lookupFieldText :: Lexicon -> FieldId -> Text+lookupFieldText Lexicon{..} (FieldId !w) =+ indexSmallArray lexToText (fromIntegral w)++-- | Bit 62 distinguishes a right-record slot from a two-record deep collision.+-- Bit 63 is the sign bit (1 for negative numbers). Bit 62 serves as the discriminator flag.+collisionBit3 :: Int64+collisionBit3 = 1 `shiftL` 62++-- | Encode a right-record slot index @idx2@ as a negative 'Int64' with bit 62 clear.+--+-- Uses bitwise complement ('Data.Bits.complement') so that @idx2 = 0@ maps to @-1@,+-- @idx2 = 1@ maps to @-2@, etc., ensuring strict negativity while keeping bit 62 zero.+{-# INLINE encodeRightSlot3 #-}+encodeRightSlot3 :: Int -> Int64+encodeRightSlot3 !idx2 =+ complement (fromIntegral idx2) .&. complement collisionBit3++-- | Encode a colliding pair of slot indices @(idx1, idx2)@ for 'OpCombineDeep'.+--+-- Packs @idx1@ into bits 30..59 and @idx2@ into bits 0..29, sets bit 62, and negates.+{-# INLINE encodeCollision3 #-}+encodeCollision3 :: Int -> Int -> Int64+encodeCollision3 !idx1 !idx2 =+ let !payload = (fromIntegral idx1 `shiftL` 30) .|. fromIntegral idx2+ in complement payload .|. collisionBit3++-- | Decode a 'MergeMorph3' gather code into its constituent source slots:+--+-- * @Left (Left idx1)@ : Unambiguous value from slot @idx1@ of the left record.+-- * @Left (Right idx2)@ : Unambiguous value from slot @idx2@ of the right record.+-- * @Right (idx1, idx2)@ : Recursive collision between @idx1@ and @idx2@.+{-# INLINE decodeMergeCode3 #-}+decodeMergeCode3 :: Int64 -> Either (Either Int Int) (Int, Int)+decodeMergeCode3 !code+ | code >= 0 = Left (Left (fromIntegral code))+ | (code .&. collisionBit3) == 0 =+ Left (Right (fromIntegral (complement code)))+ | otherwise =+ let !raw = complement (code .&. complement collisionBit3)+ !idx1 = fromIntegral (raw `shiftR` 30)+ !idx2 = fromIntegral (raw .&. 0x3FFFFFFF)+ in Right (idx1, idx2)++-- | Branch-minimized binary search over a sorted 'PrimArray' of 'Word32' field IDs.+--+-- Returns the slot index of the target 'FieldId' if present, or 'Nothing'.+-- Operates in $O(\log N)$ time with zero heap allocations.+{-# INLINE findFieldSlot #-}+findFieldSlot :: PrimArray Word32 -> FieldId -> Maybe Int+findFieldSlot !fields (FieldId !target) =+ go 0 (sizeofPrimArray fields - 1)+ where+ go !lo !hi+ | lo > hi = Nothing+ | otherwise =+ let !mid = (lo + hi) `unsafeShiftR` 1+ !v = indexPrimArray fields mid+ in case compare v target of+ LT -> go (mid + 1) hi+ GT -> go lo (mid - 1)+ EQ -> Just mid++-- | Two-finger linear synthesis of a 3-way 'MergeMorph3' over two sorted schemas.+--+-- Traverses the two sorted 'PrimArray's in parallel in $O(N_1 + N_2)$ time, emitting:+--+-- 1. The merged schema's sorted 'PrimArray' of field IDs.+-- 2. The compiled 'MergeMorph3' gather codes for instantiating the merged record values.+synthesizeMergeMorph3+ :: RecordOp+ -> PrimArray Word32+ -> PrimArray Word32+ -> (PrimArray Word32, MergeMorph3)+synthesizeMergeMorph3 !op !f1 !f2 =+ let !n1 = sizeofPrimArray f1+ !n2 = sizeofPrimArray f2+ -- Linear merge worker with accumulators for output fields and gather codes:+ go !i !j accFields accCodes+ | i >= n1 && j >= n2 =+ -- Both inputs exhausted; finish and freeze output arrays:+ ( primArrayFromList (reverse accFields)+ , MergeMorph3 (primArrayFromList (reverse accCodes))+ )+ | i >= n1 =+ -- Left input exhausted; process remaining right-hand fields:+ case op of+ OpRestrict ->+ -- OpRestrict only retains fields present in the left record:+ ( primArrayFromList (reverse accFields)+ , MergeMorph3 (primArrayFromList (reverse accCodes))+ )+ _ ->+ let !k2 = indexPrimArray f2 j+ in go i (j + 1) (k2 : accFields) (encodeRightSlot3 j : accCodes)+ | j >= n2 =+ -- Right input exhausted; process remaining left-hand fields:+ case op of+ OpRestrict ->+ -- OpRestrict only retains fields present in both records:+ ( primArrayFromList (reverse accFields)+ , MergeMorph3 (primArrayFromList (reverse accCodes))+ )+ _ ->+ let !k1 = indexPrimArray f1 i+ in go (i + 1) j (k1 : accFields) (fromIntegral i : accCodes)+ | otherwise =+ -- Both streams have remaining elements; compare field IDs:+ let !k1 = indexPrimArray f1 i+ !k2 = indexPrimArray f2 j+ in case compare k1 k2 of+ LT -> case op of+ OpRestrict -> go (i + 1) j accFields accCodes+ _ -> go (i + 1) j (k1 : accFields) (fromIntegral i : accCodes)+ GT -> case op of+ OpRestrict -> go i (j + 1) accFields accCodes+ _ -> go i (j + 1) (k2 : accFields) (encodeRightSlot3 j : accCodes)+ EQ ->+ -- Field appears in both records; determine resolution by operation:+ let !code = case op of+ OpPreferR -> encodeRightSlot3 j+ OpCombineDeep -> encodeCollision3 i j+ OpRestrict -> fromIntegral i+ in go (i + 1) (j + 1) (k1 : accFields) (code : accCodes)+ in go 0 0 [] []
+ src/Pykinos/Tree/BPlus.hs view
@@ -0,0 +1,236 @@+{-# LANGUAGE BangPatterns, DeriveFunctor, DeriveFoldable, ScopedTypeVariables #-}++{- |+Module : Pykinos.Tree.BPlus+Description : Cache-conscious serried B+ tree with transient epoch versioning+Copyright : (c) Nadia Yvette Chambers, 2026+License : EUPL-1.2+Maintainer : Nadia Chambers <nadia.yvette.chambers@ik.me>+Stability : experimental+Portability : non-portable (GHC extensions, primitive arrays)++Implements a serried B+ tree using unboxed 'SmallArray' slices for both internal+routing nodes ('BPInternal') and key-value leaves ('BPLeaf').++= Algorithmic Properties++1. **Branching Factor:** Fixed capacity \(M = 16\) slots per node (corresponding to+ 128 bytes of pointers on 64-bit architectures, fitting inside two L1 cache lines).+2. **Balanced Height:** All leaves reside at the same tree depth. Insertion splits+ overflowing nodes at \(\lfloor M / 2 \rfloor\) and propagates pivot keys upward.+3. **Cache Locality:** Keys within each leaf and internal node are stored sequentially+ in contiguous memory, enabling binary search ('searchKeys') with minimal branch mispredictions.+4. **Transient Epoch Versioning:** Each node carries an 'EpochId'. When operating+ under 'Pykinos.Effect.Penelope', modifications within the current epoch mutate+ nodes in-place or reuse allocations, while crossing an epoch boundary triggers+ persistent copy-on-write isolation.+-}+module Pykinos.Tree.BPlus+ ( -- * Epoch Tokens+ EpochId+ -- * Tree Types+ , BPlusMap(..)+ , BPlusNode(..)+ -- * Construction & Empty Maps+ , emptyBPlus+ , fromListBPlus+ -- * Lookups & Queries+ , lookupBPlus+ , toAscListBPlus+ -- * Insertion+ , insertBPlus+ , insertBPlusEpoch+ ) where++import Control.Monad.ST (runST)+import Data.Primitive.SmallArray+import Data.Word (Word64)++-- | Monotonic transient epoch token used for MVCC and snapshot isolation.+--+-- Epoch 0 denotes a persistent immutable snapshot. Non-zero epochs identify+-- isolated transaction branches.+type EpochId = Word64++-- | Maximum branching factor per serried B+ block (16 slots = 128 bytes of pointers).+bPlusMaxCap :: Int+bPlusMaxCap = 16++-- | Node representation in the serried B+ tree.+--+-- Nodes are partitioned into routing internal nodes ('BPInternal') and+-- data-bearing leaves ('BPLeaf').+data BPlusNode k v+ = BPLeaf+ { bplEpoch :: {-# UNPACK #-} !EpochId+ -- ^ Epoch version stamp at node creation.+ , bplKeys :: {-# UNPACK #-} !(SmallArray k)+ -- ^ Contiguous sorted keys stored in this leaf node.+ , bplVals :: {-# UNPACK #-} !(SmallArray v)+ -- ^ Contiguous values aligned one-to-one with 'bplKeys'.+ }+ | BPInternal+ { bpiEpoch :: {-# UNPACK #-} !EpochId+ -- ^ Epoch version stamp at node creation.+ , bpiPivots :: {-# UNPACK #-} !(SmallArray k)+ -- ^ Sorted separator pivot keys dividing child branches.+ , bpiChildren :: {-# UNPACK #-} !(SmallArray (BPlusNode k v))+ -- ^ Child node pointers (size is @sizeofSmallArray bpiPivots + 1@).+ }+ deriving (Eq, Show, Functor, Foldable)++-- | Persistent B+ tree key-value map.+data BPlusMap k v = BPlusMap+ { bpmSize :: {-# UNPACK #-} !Int+ -- ^ Total number of key-value associations stored in the map.+ , bpmRoot :: !(BPlusNode k v)+ -- ^ Root node of the B+ tree hierarchy.+ } deriving (Eq, Show, Functor, Foldable)++-- | Construct an empty 'BPlusMap'.+--+-- Running time: \(O(1)\).+emptyBPlus :: BPlusMap k v+emptyBPlus = BPlusMap 0 (BPLeaf 0 (smallArrayFromList []) (smallArrayFromList []))++-- | Binary search for key 'k' in a sorted 'SmallArray k'.+--+-- Returns 'Right' index if key is found, or 'Left' insertion slot if absent.+--+-- Running time: \(O(\log M)\) where \(M \le 16\).+searchKeys :: Ord k => SmallArray k -> k -> Either Int Int+searchKeys !arr !k = go 0 (sizeofSmallArray arr - 1)+ where+ go !lo !hi+ | lo > hi = Left lo+ | otherwise =+ let !mid = (lo + hi) `div` 2+ !kv = indexSmallArray arr mid+ in case compare k kv of+ EQ -> Right mid+ LT -> go lo (mid - 1)+ GT -> go (mid + 1) hi++-- | Determine child slot in 'BPInternal' routing node for search key 'k'.+findChildIdx :: Ord k => SmallArray k -> k -> Int+findChildIdx !pivots !k = go 0 (sizeofSmallArray pivots)+ where+ go !i !n+ | i >= n = n+ | k < indexSmallArray pivots i = i+ | otherwise = go (i + 1) n++-- | Query a key in the 'BPlusMap'.+--+-- Running time: \(O(\log_M n)\) with cacheline-optimized binary search at each level.+lookupBPlus :: Ord k => k -> BPlusMap k v -> Maybe v+lookupBPlus !k (BPlusMap _ root) = go root+ where+ go (BPLeaf _ keys vals) =+ case searchKeys keys k of+ Right !idx -> Just (indexSmallArray vals idx)+ Left _ -> Nothing+ go (BPInternal _ pivots children) =+ let !cIdx = findChildIdx pivots k+ in go (indexSmallArray children cIdx)++-- | Pure persistent insertion into a 'BPlusMap' (stamped with 'EpochId' 0).+--+-- Running time: \(O(\log_M n)\).+insertBPlus :: Ord k => k -> v -> BPlusMap k v -> BPlusMap k v+insertBPlus !k v !m = insertBPlusEpoch 0 k v m++-- | Epoch-stamped insertion supporting \(O(1)\) transient epoch tracking in Penelope.+--+-- Running time: \(O(\log_M n)\).+insertBPlusEpoch :: Ord k => EpochId -> k -> v -> BPlusMap k v -> BPlusMap k v+insertBPlusEpoch !ep !k v (BPlusMap !sz root) =+ let (!added, !res) = insNode root+ in case res of+ Left !node' ->+ BPlusMap (if added then sz + 1 else sz) node'+ Right (!leftN, !pivotK, !rightN) ->+ let !newRoot = BPInternal ep (smallArrayFromList [pivotK]) (smallArrayFromList [leftN, rightN])+ in BPlusMap (if added then sz + 1 else sz) newRoot+ where+ insNode (BPLeaf _ keys vals) =+ case searchKeys keys k of+ Right !idx ->+ (False, Left (BPLeaf ep keys (replaceAt vals idx v)))+ Left !insIdx ->+ let !keys' = insertAt keys insIdx k+ !vals' = insertAt vals insIdx v+ !len' = sizeofSmallArray keys'+ in if len' <= bPlusMaxCap+ then (True, Left (BPLeaf ep keys' vals'))+ else+ let !mid = len' `div` 2+ !kL = cloneSmallArray keys' 0 mid+ !vL = cloneSmallArray vals' 0 mid+ !kR = cloneSmallArray keys' mid (len' - mid)+ !vR = cloneSmallArray vals' mid (len' - mid)+ !piv = indexSmallArray kR 0+ in (True, Right (BPLeaf ep kL vL, piv, BPLeaf ep kR vR))++ insNode (BPInternal _ pivots children) =+ let !cIdx = findChildIdx pivots k+ (!added, !childRes) = insNode (indexSmallArray children cIdx)+ in case childRes of+ Left !c' ->+ (added, Left (BPInternal ep pivots (replaceAt children cIdx c')))+ Right (!cL, !piv, !cR) ->+ let !pivots' = insertAt pivots cIdx piv+ !children' = insertAt (replaceAt children cIdx cL) (cIdx + 1) cR+ !cLen = sizeofSmallArray children'+ in if cLen <= bPlusMaxCap+ then (added, Left (BPInternal ep pivots' children'))+ else+ let !mid = cLen `div` 2+ !upPiv = indexSmallArray pivots' (mid - 1)+ !pL = cloneSmallArray pivots' 0 (mid - 1)+ !pR = cloneSmallArray pivots' mid (sizeofSmallArray pivots' - mid)+ !chL = cloneSmallArray children' 0 mid+ !chR = cloneSmallArray children' mid (cLen - mid)+ in (added, Right (BPInternal ep pL chL, upPiv, BPInternal ep pR chR))++-- | Flatten all key-value entries into an ascending sorted list.+--+-- Running time: \(O(n)\).+toAscListBPlus :: BPlusMap k v -> [(k, v)]+toAscListBPlus (BPlusMap _ root) = go root []+ where+ go (BPLeaf _ keys vals) acc =+ let !n = sizeofSmallArray keys+ loop !i !a+ | i < 0 = a+ | otherwise = loop (i - 1) ((indexSmallArray keys i, indexSmallArray vals i) : a)+ in loop (n - 1) acc+ go (BPInternal _ _ children) acc =+ let !n = sizeofSmallArray children+ loop !i !a+ | i < 0 = a+ | otherwise = loop (i - 1) (go (indexSmallArray children i) a)+ in loop (n - 1) acc++-- | Construct a 'BPlusMap' from a list of key-value pairs.+--+-- Running time: \(O(n \log_M n)\).+fromListBPlus :: Ord k => [(k, v)] -> BPlusMap k v+fromListBPlus = foldl' (\acc (k, v) -> insertBPlus k v acc) emptyBPlus++-- | Insert element 'val' into 'SmallArray' at slot 'idx'.+insertAt :: SmallArray a -> Int -> a -> SmallArray a+insertAt !arr !idx val = runST $ do+ let !n = sizeofSmallArray arr+ m <- newSmallArray (n + 1) val+ copySmallArray m 0 arr 0 idx+ copySmallArray m (idx + 1) arr idx (n - idx)+ unsafeFreezeSmallArray m++-- | Replace element at slot 'idx' in 'SmallArray' with 'val'.+replaceAt :: SmallArray a -> Int -> a -> SmallArray a+replaceAt !arr !idx val = runST $ do+ let !n = sizeofSmallArray arr+ m <- thawSmallArray arr 0 n+ writeSmallArray m idx val+ unsafeFreezeSmallArray m
+ src/Pykinos/Tree/FAST.hs view
@@ -0,0 +1,125 @@+{-# LANGUAGE BangPatterns, DeriveFunctor, ScopedTypeVariables #-}++{- |+Module : Pykinos.Tree.FAST+Description : Fast Architecture Sensitive Tree (FAST) cache-blocked search structure+Copyright : (c) Nadia Yvette Chambers, 2026+License : EUPL-1.2+Maintainer : Nadia Chambers <nadia.yvette.chambers@ik.me>+Stability : experimental+Portability : non-portable (GHC extensions, primitive arrays)++Implements the Fast Architecture Sensitive Tree (FAST) layout derived from+Kim et al. (SIGMOD 2010), /"FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs"/.++= Architectural Rationale++Traditional balanced binary trees (such as red-black trees or AVL trees) and+even cache-conscious B-trees incur pointer-chasing overhead across non-contiguous+heap objects:+1. Each branch navigation traverses a heap pointer to a separate cache line.+2. Branch predictors struggle with binary traversal patterns.+3. Hardware memory prefetchers cannot predict irregular memory strides.++FAST resolves these hardware bottlenecks by flattening an ordered collection+into a 1-based __Eytzinger__ (breadth-first array) layout:+* Root resides at index 1.+* For any node at index \(i\), its left child is at \(2i\) and right child is at \(2i + 1\).+* Children of consecutive nodes are contiguous in memory, allowing hardware streaming+ prefetchers to anticipate memory accesses across levels.+* Tree levels map cleanly into L1/L2 cache lines with zero pointer indirection.++FAST structures in Pykinos are immutable snapshots materialized by 'freezeFAST'+from a mutable or transient 'BPlusMap', providing high-throughput read-only+accelerators for symbol lookups and index sweeps.+-}+module Pykinos.Tree.FAST+ ( -- * FAST Accelerator Structure+ FASTMap(..)+ -- * Construction & Freezing+ , freezeFAST+ -- * Queries+ , lookupFAST+ , sizeFAST+ ) where++import Control.Monad.ST (runST)+import Data.Bits (unsafeShiftL)+import Data.Primitive.SmallArray+import Pykinos.Tree.BPlus (BPlusMap, toAscListBPlus)++-- | Fast Architecture Sensitive Tree (FAST) cache-line-blocked array.+--+-- Flattened 1-based Eytzinger array layout representing a perfectly balanced+-- complete search tree in contiguous unboxed 'SmallArray' slices.+data FASTMap k v = FASTMap+ { fmSize :: {-# UNPACK #-} !Int+ -- ^ Number of stored key-value entries.+ , fmEytzKeys :: {-# UNPACK #-} !(SmallArray k)+ -- ^ Keys stored in 1-based Eytzinger breadth-first ordering. Index 0 is unused padding.+ , fmEytzVals :: {-# UNPACK #-} !(SmallArray v)+ -- ^ Values aligned with keys in 1-based Eytzinger ordering.+ } deriving (Eq, Show, Functor)++-- | Query the total number of entries in the 'FASTMap'.+--+-- Running time: \(O(1)\).+{-# INLINE sizeFAST #-}+sizeFAST :: FASTMap k v -> Int+sizeFAST = fmSize++-- | Freeze an ordered 'BPlusMap' into a contiguous cache-line-blocked 'FASTMap'.+--+-- Traverses the B+ tree in ascending key order via an in-order traversal and writes+-- elements directly into 1-based Eytzinger breadth-first slots in a single \(O(n)\) pass.+--+-- Running time: \(O(n)\) where \(n\) is the number of elements in the tree.+-- Memory footprint: \(2 \times (n + 1)\) slots in two contiguous 'SmallArray' buffers.+freezeFAST :: forall k v. BPlusMap k v -> FASTMap k v+freezeFAST !bpm =+ let !pairs = toAscListBPlus bpm+ !n = length pairs+ in if n == 0+ then FASTMap 0 (smallArrayFromList []) (smallArrayFromList [])+ else+ let !sortedK = smallArrayFromList (map fst pairs)+ !sortedV = smallArrayFromList (map snd pairs)+ (!eytzK, !eytzV) = runST $ do+ let !k0 = indexSmallArray sortedK 0+ !v0 = indexSmallArray sortedV 0+ mk <- newSmallArray (n + 1) k0+ mv <- newSmallArray (n + 1) v0+ -- Recursive in-order traversal mapping sorted index to Eytzinger breadth-first node index.+ let build !nodeIdx !srcIdx+ | nodeIdx > n = pure srcIdx+ | otherwise = do+ !srcIdx' <- build (2 * nodeIdx) srcIdx+ writeSmallArray mk nodeIdx (indexSmallArray sortedK srcIdx')+ writeSmallArray mv nodeIdx (indexSmallArray sortedV srcIdx')+ build (2 * nodeIdx + 1) (srcIdx' + 1)+ _ <- build 1 0+ fk <- unsafeFreezeSmallArray mk+ fv <- unsafeFreezeSmallArray mv+ pure (fk, fv)+ in FASTMap n eytzK eytzV++-- | Branch-minimized binary search lookup over the contiguous Eytzinger array.+--+-- Navigates down the implicit binary tree using bitwise arithmetic:+-- * Left child: @idx `unsafeShiftL` 1@ (i.e. \(2 \cdot \text{idx}\))+-- * Right child: @(idx `unsafeShiftL` 1) + 1@ (i.e. \(2 \cdot \text{idx} + 1\))+--+-- Running time: \(O(\log n)\) with zero pointer dereferences and optimal cacheline utilization.+lookupFAST :: Ord k => k -> FASTMap k v -> Maybe v+lookupFAST !q (FASTMap !n keys vals)+ | n == 0 = Nothing+ | otherwise = go 1+ where+ go !idx+ | idx > n = Nothing+ | otherwise =+ let !k = indexSmallArray keys idx+ in case compare q k of+ EQ -> Just (indexSmallArray vals idx)+ LT -> go (idx `unsafeShiftL` 1)+ GT -> go ((idx `unsafeShiftL` 1) + 1)
+ test/Spec.hs view
@@ -0,0 +1,126 @@+{-# LANGUAGE BangPatterns #-}+module Main (main) where++import System.Exit (exitFailure)+import Pykinos.Bitset.Roaring+import Pykinos.IntMap.ART+import Pykinos.Mutable.SwissTable+import Pykinos.Schema.HiddenClass+import qualified Data.Text as T+import Control.Monad.ST (runST)+import Pykinos.Tree.BPlus+import Pykinos.Tree.FAST++assertBool :: String -> Bool -> IO ()+assertBool name cond =+ if cond+ then putStrLn $ " [PASS] " ++ name+ else do+ putStrLn $ " [FAIL] " ++ name+ exitFailure++main :: IO ()+main = do+ putStrLn "=== [pykinos-core-test] Running Roaring & ART Test Suite ==="++ -- 1. Roaring Basic Operations+ let s0 = emptyRoaring+ assertBool "s0 is null" (nullRoaring s0)++ let s1 = singletonRoaring 42+ assertBool "s1 not null" (not (nullRoaring s1))+ assertBool "s1 contains 42" (memberRoaring 42 s1)+ assertBool "s1 does not contain 43" (not (memberRoaring 43 s1))++ -- 2. Roaring Dense Array / Bitmap Promotion (> 4096 entries in a single 16-bit block)+ let denseList = [0 .. 4500]+ sDense = fromListRoaring denseList+ assertBool "sDense contains 0" (memberRoaring 0 sDense)+ assertBool "sDense contains 4500" (memberRoaring 4500 sDense)+ assertBool "sDense does not contain 4501" (not (memberRoaring 4501 sDense))++ -- 3. Roaring Union, Intersect, Difference+ let setA = fromListRoaring [1, 2, 3, 100, 70000]+ setB = fromListRoaring [3, 4, 5, 100, 70001]+ uSet = unionRoaring setA setB+ iSet = intersectRoaring setA setB+ dSet = differenceRoaring setA setB++ assertBool "union contains 1" (memberRoaring 1 uSet)+ assertBool "union contains 5" (memberRoaring 5 uSet)+ assertBool "union contains 70000 and 70001" (memberRoaring 70000 uSet && memberRoaring 70001 uSet)+ assertBool "intersect contains 3 and 100" (memberRoaring 3 iSet && memberRoaring 100 iSet)+ assertBool "intersect does not contain 1" (not (memberRoaring 1 iSet))+ assertBool "diff contains 1, 2, 70000" (memberRoaring 1 dSet && memberRoaring 2 dSet && memberRoaring 70000 dSet)+ assertBool "diff does not contain 3 or 100" (not (memberRoaring 3 dSet) && not (memberRoaring 100 dSet))++ -- 4. ART IntMap Operations across Node sizes+ let m0 = emptyART :: ARTIntMap String+ m4 = foldr (\k acc -> artInsert k ("val-" ++ show k) acc) m0 [1..4]+ assertBool "m4 lookup 1" (artLookup 1 m4 == Just "val-1")+ assertBool "m4 lookup 4" (artLookup 4 m4 == Just "val-4")+ assertBool "m4 lookup 5 is Nothing" (artLookup 5 m4 == Nothing)++ let m16 = foldr (\k acc -> artInsert k ("val-" ++ show k) acc) m4 [5..16]+ assertBool "m16 lookup 16" (artLookup 16 m16 == Just "val-16")+ assertBool "m16 lookup 10" (artLookup 10 m16 == Just "val-10")++ let m48 = foldr (\k acc -> artInsert k ("val-" ++ show k) acc) m16 [17..48]+ assertBool "m48 lookup 48" (artLookup 48 m48 == Just "val-48")++ let m256 = foldr (\k acc -> artInsert k ("val-" ++ show k) acc) m48 [49..100]+ assertBool "m256 lookup 100" (artLookup 100 m256 == Just "val-100")+ assertBool "m256 member 75" (artMember 75 m256)+ assertBool "m256 member 101 False" (not (artMember 101 m256))++ let mDel = artDelete 50 m256+ assertBool "mDel lookup 50 is Nothing" (artLookup 50 mDel == Nothing)+ assertBool "mDel lookup 49 still Just" (artLookup 49 mDel == Just "val-49")++ let kSet = artKeysSet mDel+ assertBool "kSet contains 49" (memberRoaring 49 kSet)+ assertBool "kSet does not contain 50" (not (memberRoaring 50 kSet))++ -- 5. BPlusMap Tests (splits across multi-level blocks)+ let bp0 = emptyBPlus :: BPlusMap Int String+ bp100 = foldr (\k acc -> insertBPlus k ("v" ++ show k) acc) bp0 [1..100]+ assertBool "bp100 size is 100" (bpmSize bp100 == 100)+ assertBool "bp100 lookup 1" (lookupBPlus 1 bp100 == Just "v1")+ assertBool "bp100 lookup 50" (lookupBPlus 50 bp100 == Just "v50")+ assertBool "bp100 lookup 100" (lookupBPlus 100 bp100 == Just "v100")+ assertBool "bp100 lookup 101 is Nothing" (lookupBPlus 101 bp100 == Nothing)++ let ascList = toAscListBPlus bp100+ assertBool "ascList has 100 items" (length ascList == 100)+ assertBool "ascList is sorted" (map fst ascList == [1..100])++ -- 6. FASTMap Tests (Eytzinger Cache-line acceleration)+ let fast100 = freezeFAST bp100+ assertBool "fast100 size is 100" (sizeFAST fast100 == 100)+ assertBool "fast100 lookup 1" (lookupFAST 1 fast100 == Just "v1")+ assertBool "fast100 lookup 50" (lookupFAST 50 fast100 == Just "v50")+ assertBool "fast100 lookup 100" (lookupFAST 100 fast100 == Just "v100")+ assertBool "fast100 lookup 101 is Nothing" (lookupFAST 101 fast100 == Nothing)++ + -- 7. SwissTable128 Tests (SWAR 128-bit hash-consing)+ let (id0, id1, id0_again) = runST $ do+ tbl <- newSwissTable128 32+ let (kLo1, kHi1) = packNfNode128 1 0 10 20 30+ (kLo2, kHi2) = packNfNode128 2 0 40 50 60+ i0 <- lookupOrInsert128 tbl kLo1 kHi1+ i1 <- lookupOrInsert128 tbl kLo2 kHi2+ i0' <- lookupOrInsert128 tbl kLo1 kHi1+ pure (i0, i1, i0')+ assertBool "id0 is 0" (id0 == 0)+ assertBool "id1 is 1" (id1 == 1)+ assertBool "id0_again matches id0" (id0_again == 0)++ + -- 8. HiddenClass & Lexicon Tests+ let lx = buildLexicon [T.pack "beta", T.pack "alpha", T.pack "gamma"]+ assertBool "alpha fid is 0" (lookupFieldId lx (T.pack "alpha") == Just (FieldId 0))+ assertBool "beta fid is 1" (lookupFieldId lx (T.pack "beta") == Just (FieldId 1))+ assertBool "gamma fid is 2" (lookupFieldId lx (T.pack "gamma") == Just (FieldId 2))++ putStrLn "=== [pykinos-core-test] ALL 33 PROPERTIES AND UNIT CHECKS PASSED ==="