Re: [dev] [RFC] Design of a vim like text editor

From: Maxime Coste <frrrwww_AT_gmail.com>
Date: Wed, 17 Sep 2014 00:03:55 +0100

On Tue, Sep 16, 2014 at 11:20:45PM +0200, Roberto E. Vargas Caballero wrote:
> > Ok, so what exactly is the sum of 3 lines and 2 bytes ? The whole point
> > is to catch at compilation code that is logically invalid, if you have
> > f(ByteCount, LineCount), you cannot call it with a (LineCount, ByteCount)
> > signature. In C you would be forced to use f(int, int), and long debugging
> > sessions to discover this simple mistake.
>
> Can you explain me why in C you have to represent them as int or long as
> not with a structure like you did in c++?.

Because I want the convenience of adding two byte counts using +, which I can
do in C++, and have that compile down to exactly the same assembly as if I used ints,
but still get a compilation error if I try to add a byte count and a line count.
 
> > It just gives you tool so that you can write your code closed to the domain
> > language, did you learn linear algebra writing matrix_add(m1, m2, &m3)
> > ? or m3 = m1 + m2 ?
>
> It is only useful in some algebra cases where usually is better
> incorporate them into the language instead of this user overloading.
> Can you explaing me what is the meaning of '+' when you have for example
> two lines? the addition one by one of each element or the concatenation
> of them?.

Why would I overload the addition on lines ? As you say, there is no canonical
operation that makes sense for that. I use operator overloading only on types
where they match their semantic.

> I have worked in complex code bases written in C++, where the use of C++
> did that was impossible to keep them in the brain. In all the other
> projects C and a correct division between tools make that programs can
> keep in my mind. If you have pointers that are allocated in some place
> and freed in another place then you code should be written in another way.
> A good book for you could be 'The practice of programming'.

I work on video games technologies, we have a multi milion lines code base,
written by 100+ people, we need to be able to organize it and to provide
abstraction because nobody can fit the whole thing in his mind.
 
> Try to don't need such kind of things. For example Go hasn't generic and
> you don't need them ever. You like them because your are so used to them
> that you don't see the kind of code you are forced to write with them.

That is the complaint I mostly hear about Go, the lack of Generic. That and
garbage collection.
 
> > Get your complexity right, inserting in a dynamic array is O(n), the eventual
> > need for an allocation is amortized (whereas you always end up doing a malloc
> > for your linked lists). Another thing you should look up is modern cpu
>
> No. Because the realloc that you have to do maybe has to move in the
> worst case n-1 elements in a new memory arena. So you have n (moving
> to the position) * n-1 (memcpy to new position in memory) = n^2. You
> can decrease the possibility of reallocation allocating
> more memory of needed, but when you have the reallocation you get
> the O(n^2). In a list you don't have ever a reallocation.

You already answered that.
 
> If you read what I have said, iy you insert in the HEAD, and always take
> the HEAD (FIFO fashion), you don't get any problem of locality, because
> you directly access (or remove) the element you need. And now that you
> are talking about deletion in dinamyc arrays, can you explain me how do you
> delete in the middle of them?. AFAIK there are only two ways:
>
> [...]

Ok, so on a modern processor, data access pattern matters, with your linked list,
you basically have a cache miss at each access to the next element when you iterate,
when you use an array, you get linear access in memory, which means you please the
prefetcher and avoid most cache misses. That effect on performance is huge, and
in practice largely dominate the algorithmic complexity.

Additionally, the storage overhead of the linked list is interleaved with the
payload, which means you stress even more your memory accesses.

Cheers,

Maxime.
Received on Wed Sep 17 2014 - 01:03:55 CEST