Re: Size and length limits for Emacs primitive types and etc data?

[Oleksandr Gavenko]

On 2013-02-05, Burton Samograd wrote:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>>> I think linked nature of elisp data structure cause very high rate of CPU
>>> cache miss (but I don't actually run any AMD/Intel CPU profilers).
>>
>> Prove it.
>
I don't familiar with appropriated CPU profilers:

  
http://developer.amd.com/tools/heterogeneous-computing/amd-codeanalyst-performance-analyzer/
                CodeAnalyst Performance Analyzer
  http://developer.amd.com/tools/heterogeneous-computing/codexl/
                GPU debugging, comprehensive GPU and CPU profiling, and static
                OpenCL™ kernel analysis capabilities

  http://software.intel.com/en-us/intel-vtune-amplifier-xe
                Intel® VTune™ Amplifier XE 2013 is the premier profiler for C,
                C++, C#, Fortran, Assembly and Java.

Main reason that it is hard to interpret right what they show (modern CPU have
too complicate execution architecture).

> Here's an analysis of cache misses with pointer based data structures
> (linked list and trees):
>
>   http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.9669
>
> It's common knowledge that linked lists are not cache friendly, leading
> to creation of structures like Unrolled Linked Lists
> (http://en.wikipedia.org/wiki/Unrolled_linked_list) to help.
>

I work with Isabelle proof assistant (written in ML) on my old laptop with 512
MiB of RAM (in 64-bit userspace). On large theories my laptop froze on disk
(swap) operations. While non-functional programs like Firefox and OpenOffice
operated with minor slowness in IU when out of 512 MiB.

It is possible to say that I run into 100% RAM misses!!

After installing additional memory module (up to 1 GiB) any disk operation go
away on those large theories!

Also interesting result we get when work on optimisation of GOST cipher. It
have permutation table and in order to increase speed we expand this table.
Usually larger precomputation give better performance... but in our case as
soon table out of CPU cache we lose speed in 2 or more times...

Deduce from theoretical positions (look to Burton Samograd link) it is
possible frequently cache misses in Elisp. As I don't know GNU Emacs internals
I ask about Elisp and CPU cache misses...

-- 
Best regards!