[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Overlays as an AA-tree
From: |
Andreas Politz |
Subject: |
Re: Overlays as an AA-tree |
Date: |
Tue, 21 Feb 2017 19:26:20 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) |
Stefan Monnier <address@hidden> writes:
> BTW, in your new overlay representation, how many bytes (or words) does
> an overlay cost (in the master tree, if I count right, an overlay costs
> 3 Lisp_Misc objects, so that should be 3x 6words, i.e. 72 bytes on
> a 32bit system)?
>
> I'd expect the new representation to be no larger (the current
> representation has a lot of redundancy). But I'm curious because,
> depending on the answer, the whole Lisp_Misc thingy might want to
> be reconsidered.
>
I don't' know how you're counting, so here is how I (or rtags) would.
#+BEGIN_SRC c
/* master */
struct Lisp_Overlay
{
ENUM_BF (Lisp_Misc_Type) type : 16;
bool_bf gcmarkbit : 1;
unsigned spacer : 15;
struct Lisp_Overlay *next;
Lisp_Object start; /* -> 40 bytes */
Lisp_Object end; /* -> 40 bytes */
Lisp_Object plist; /* -> 40 bytes */
}; /* 40 bytes */
/* Total: 40 + 3*40 = 160 */
/* noverlay */
struct Lisp_Overlay
{
ENUM_BF (Lisp_Misc_Type) type : 16;
bool_bf gcmarkbit : 1;
unsigned spacer : 15;
Lisp_Object plist; /* -> 40 bytes */
struct buffer *buffer;
struct interval_node *interval;
}; /* 32 bytes */
struct interval_node /* layout tweaked */
{
struct interval_node *parent;
struct interval_node *left;
struct interval_node *right;
ptrdiff_t begin; /* The beginning of this interval. */
ptrdiff_t end; /* The end of the interval. */
ptrdiff_t limit; /* The maximum end in this subtree. */
ptrdiff_t offset; /* The amount of shift to apply to this subtree.
*/
uintmax_t otick; /* offset modified tick */
Lisp_Object data; /* Exclusively used by the client. */
bool_bf visited : 1; /* For traversal via generator. */
bool_bf rear_advance : 1; /* Same as for marker and overlays. */
bool_bf front_advance : 1; /* Same as for marker and overlays. */
enum { ITREE_RED, ITREE_BLACK } color : 1;
}; /* 80 bytes */
/* Total: 32 + 40 + 80 = 152 */
#+END_SRC
-ap
- Re: Overlays as an AA-tree, (continued)
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/16
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/17
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/19
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/20
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree,
Andreas Politz <=
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/24
- Re: Overlays as an AA-tree, Richard Stallman, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/14
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/06
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Clément Pit-Claudel, 2017/02/06