René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Object representation","articleBody":"Your representation of objects is of particular bad design.\r\n\r\nLet's examine how much memory we need to store an integer on the stack frame or in a vector. You need to store `PyObjectRef`, that's `Rc\u003cRefCell\u003cPyObject\u003e\u003e`, that's one pointer (64 bit), one strong reference counter (64 bit), one weak reference counter (64 bit), one borrow counter (64 bit). The strong and weak reference counters and the borrow counter are to be initialized each time a pointer is created.\r\n\r\nThe type `PyObject` consists of `payload: PyObjectPayload` and `typ: Option\u003cPyObjectRef\u003e`. That's again a pointer (64 bit), the `Option::None` is stored as a pointer to NULL, as `PyObjectRef` is non-NULL. The type `PyObjectPayload` is a large enum, 8 up to 64 bit for a tag, and the variant `Integer` stores `BigInt`. `BigInt` consists of `sign: Sign` (8 up to 64 bit) and `data: BigUint` (`Vec\u003cBigDigit\u003e`) (64 bit pointer, 64 bit capacity, 64 bit size). A BigDigit is an `u32`.\r\n\r\nThat's 70 Byte up to 84 Byte for each integer. There are three(!) pointer indirections and eleven(!) memory slots to be initialized. Fragmentation of the allocatator will result in catastrophically bad cache locality. At object destruction, the `PyObjectPayload` enum is branched (hopefully by a branchtable), but as the number of variants is large, it will be a subroutine call (otherwise the branchtable is shadowed by another branch).\r\n\r\nNow consider the following object representation:\r\n```rust\r\ntrait RefTrait {}\r\ntype DynRef = dyn RefTrait;\r\n// You can create your own vtables instead of using dyn,\r\n// given there is an unsolveable issue with dyn.\r\n\r\nenum PyObject {\r\n    None,\r\n    Bool(bool),\r\n    Int(i64),\r\n    Float(f64),\r\n    Complex(Complex64), // (f64,f64)\r\n    Ref(Rc\u003cRefCell\u003cDynRef\u003e\u003e)\r\n}\r\n```\r\nThe tag stores 8 up to 64 bit. The maximal variants are `(f64,f64)` and `(Rc,VTablePointer)`, that's two times 64 bit. This results in 17 Byte up to 24 Byte. Only two memory slots need to be initialized. No memory allocations. Best cache locality.\r\n\r\nAt object destruction, only one branch is needed to determine whether the polymorphic destructor of variant `Ref` is to be called or not. This branch should be inlined.","author":{"url":"https://github.com/JohnBSmith","@type":"Person","name":"JohnBSmith"},"datePublished":"2019-02-06T17:09:16.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":17},"url":"https://github.com/371/RustPython/issues/371"}