Recent

Author Topic: Checking Speed of SynEdit Highlighters  (Read 90164 times)

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #60 on: October 24, 2013, 07:36:01 pm »
For pascal you need at least a sequence of 6 
operator  + property = operty

Dont know what you mean with that;

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 6622
  • Debugger - SynEdit - and more
    • wiki
Re: Checking Speed of SynEdit Highlighters
« Reply #61 on: October 24, 2013, 08:05:41 pm »
Ok, I had not looked at your changes.

You added the length into the compare... (I thought, you may have added another 0..25 to the array.

Try

  if IsKeyWord('object') then Caption :=  Caption + '1';
  if IsKeyWord('except') then Caption :=  Caption + '2';
  if IsKeyWord('objept') then Caption :=  Caption + '3';

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #62 on: October 24, 2013, 08:17:55 pm »
Ok, I had not looked at your changes.

You added the length into the compare... (I thought, you may have added another 0..25 to the array.

Try

  if IsKeyWord('object') then Caption :=  Caption + '1';
  if IsKeyWord('except') then Caption :=  Caption + '2';
  if IsKeyWord('objept') then Caption :=  Caption + '3';

Thanks for testing.
More dimensions are a possible solution.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 6622
  • Debugger - SynEdit - and more
    • wiki
Re: Checking Speed of SynEdit Highlighters
« Reply #63 on: October 24, 2013, 08:26:36 pm »
It can be solved, if all keywords are known (llike pascal).

But if I can add my own lists of keywords, I can probably always add 2 keywords, that allow a 3rd none keyword.


Instead a proper prefix tree should be used.

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #64 on: October 24, 2013, 08:40:36 pm »
It can be solved, if all keywords are known (llike pascal).

But if I can add my own lists of keywords, I can probably always add 2 keywords, that allow a 3rd none keyword.


Instead a proper prefix tree should be used.

Another try.
A tree would save memory, but slow down.
A sparce matrix would be faster.

howardpc

  • Hero Member
  • *****
  • Posts: 3523
Re: Checking Speed of SynEdit Highlighters
« Reply #65 on: October 25, 2013, 12:34:25 am »
Thanks for sharing your code.
There's no denying it is lightning fast.
However the algorithm is flawed. Even your latest revision (3) matches all kinds of words (am, an, any, ask, ox, them) and non-words (ia, nia) which are not Pascal keywords.
I prefer a slower algorithm that correctly matches what it says on the tin.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 6622
  • Debugger - SynEdit - and more
    • wiki
Re: Checking Speed of SynEdit Highlighters
« Reply #66 on: October 25, 2013, 01:02:38 am »
  if IsKeyWord('interface') then Caption :=  Caption + '1';
  if IsKeyWord('inherited') then Caption :=  Caption + '2';
  if IsKeyWord('interited') then Caption :=  Caption + '3';


A prefix tree (trie) is like a matrix.

It is not a binary tree. each node can have a child for each letter. So each node holds an array[0..25] with poithers to the next node (if there is)

http://en.wikipedia.org/wiki/Trie

Only potential slow down is cache misses due to mem usage.
 
Such a trie exists in SYnEdit (MarkupHighlightAll).

sam707

  • Guest
Re: Checking Speed of SynEdit Highlighters
« Reply #67 on: October 25, 2013, 01:07:45 am »
Hi

I remember 1st time when I saw hash codes and tables : It was in 1979 when I disassembled microsoft level2 basic rom on my TRS-80 machine. These days, it was clever because :

1) the kewords were transformed to 1 byte in small ram
2) the original program listing was reconstituted, doing the opposite way
3) apple computers' basic interpreter did not have such assembler tokenization, they lost

If you want to implement a compression tool, a dictionary or a hash table, even a boolean or huffman like tree can be, for sure, helpful.

but in the case of a highlighter, compression is not the goal. I suppose that there could be faster ways, maybe a sorted list of all allowed keyword. As it is a sorted constant, a kind of 'prediction' -proceeding by elimination- can be make with a character scanner that abandon the seach instant when match fails.

This way of Highlight may break the "tradition" but also may have a chance to be the faster one, since nowadays the original text will stay in memory (no need to shrink like in 1980 when ram was so damn expensive, and when programmers used/invented tokens/hash tables for that shrinking purpose).

If you still believe in hash codes, ask yourself a few questions :

- I plan to spare memory, like around 1980 when I had 16Kb of ram only? no
- hash codes will be used to keep coordinates of font changing? no
- hash codes are going to help for a dichotomic seach on an orderd constant list? no, it is ordered !
... and so on

and the Light will come to you  O:-)
« Last Edit: October 25, 2013, 02:02:18 am by sam707 »

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #68 on: October 25, 2013, 02:19:53 am »
I prefer a slower algorithm that correctly matches what it says on the tin.

Agreed.
Its a bit callow now, will have to loock for a sparse and dynamic solution.

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #69 on: October 25, 2013, 02:30:16 am »
Such a trie exists in SYnEdit (MarkupHighlightAll).

Thanks.
A trie is not a Tree in the usual meaning.

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #70 on: October 25, 2013, 02:55:18 am »
@sam707
Thanks.
I have been teached to program a 4 bit computer in machine language,
not assembler as it did not had enoug memory for an assembler.
It had no display only lamps.
1979 I got my fist with a single line display and a keyboard with letters.
My first PC 1983 was a Toshiba T300, with CPM and DOS on floppies,
without a disk.
prices had been grazy at this time.
The list prices of the t300 and a little softwares summed up to over 20000 DM.
I remember those tricks needed to do something with extremely little memory.

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8731
  • FPC developer.
Re: Checking Speed of SynEdit Highlighters
« Reply #71 on: October 25, 2013, 01:43:25 pm »
I remember those tricks needed to do something with extremely little memory.

(If you feel the need to practice, FPC/trunk now has a 16-bit tiny memorymodel)

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #72 on: October 25, 2013, 03:26:22 pm »
(If you feel the need to practice, FPC/trunk now has a 16-bit tiny memorymodel)

At the moment I squeeze 256 bytes plus some more info in 48 bytes;
Lets see how much it will slow down.

An array[byte] of BitBool occupying only 32byte would some times still be handy.
Canot find my libraries for this kind of stuff anymore;
« Last Edit: October 25, 2013, 03:53:16 pm by Morton »

sam707

  • Guest
Re: Checking Speed of SynEdit Highlighters
« Reply #73 on: October 25, 2013, 04:58:51 pm »
@sam707
Thanks.
I have been teached to program a 4 bit computer in machine language,
not assembler as it did not had enoug memory for an assembler.
It had no display only lamps.
1979 I got my fist with a single line display and a keyboard with letters.
My first PC 1983 was a Toshiba T300, with CPM and DOS on floppies,
without a disk.
prices had been grazy at this time.
The list prices of the t300 and a little softwares summed up to over 20000 DM.
I remember those tricks needed to do something with extremely little memory.

me too , it was an UC-EMR 4bits with 6 digits display.

I was so proud, after I worked a whole afternoon with octal tables as machine codes references on it, to make it display the word 'CHAIRS' on its lamps display, ancestor of LCD... hahahah

Even before that I learnt to program on a Texas Instrument SR-52 , with 223 steps of program only (I can call them by their names , see ;) ) and on that SR-52 with 223 steps (which wern't bytes) possible of programmation I played a "Lunar Landing game".

http://www.rskey.org/CMS/index.php/7?manufacturer=Texas+Instruments&model=SR-52

thx @Morton, we should please end, because I'm now feeling old and I hate to remember when I discovered an abacus between the knees of Cleopatra Queen :D

what I wanted to explain into my last postS, is the fact that in computing science, if you don't break traditions, you won't go ahead. My idea of a 'prediction" algorithm might be useful : it opens the door to a future code completion tool, that is cool to a highlighter.

combining dichotomic search on a constant ordered list that gives up instant when no more matching, plus keeping predictive track if you need future code completion, might be a cool clue.

I agree with you (and the others on that post) upon the fact that SynEdit was written years ago, following a tradition with hashcodes that sound useless to a highlighter.

Cheers
« Last Edit: October 26, 2013, 02:46:53 am by sam707 »

Morton

  • Full Member
  • ***
  • Posts: 111
Re: Checking Speed of SynEdit Highlighters
« Reply #74 on: October 25, 2013, 06:42:04 pm »
I agree with you (and the others on that post) upon the fact that SynEdit was written years ago, following a tradition with hashcodes that sound useless to a highlighter.

Thanks for your post.
For Delphi I could not find anything better.
Delphi is extremely good in inlining small methods even in in the method call tables.
In acknowledgement of my work, while I published regularly something,
I used to get free copies of professional tools.
Some with regular prices in thousands of $.
Among these was AQTime a very good binary profiler.
With it I got the CPU time spent on any piece of code with extreme precision.

BTH I think I will implement the macher with sets, just 4 bytes
instead of 256 for each dimension.
Thus lots more dimensions can be used.
with records or objects additional information can be provided vor each cell
and the matrix still keept much smaller
On my PC FPC can perform about 128 million insertions or deletions on sets per second and just accessing sets is even faster.

For small keys with few chars comparision could maybe not avoided.
The keys could be assigned to the cell for them, but maybe it can be avoided
by other means.
We will see.
If i was seriously enough behind something I could always find a solution.
« Last Edit: October 25, 2013, 07:35:55 pm by Morton »

 

TinyPortal © 2005-2018