My C homework

[motorollin]

Every time I see the subject line of this thread I think it says "Mel C's homework" :lol:

Girl Power!

--
moto

[mgerics]

Link to fre books on c and the like:
http://www.computer-books.us/c.php

[Karlos]

@Mel

Since your 030 has only 256 bytes of data cache, you might want to redesign your character table like so:

Code: [Select]


static unsigned long chartypedata[8] = { 0 };

#define isword(c) (chartypedata[(c)>>5]&(1UL<<((c)&31UL)))
#define setbit_isword(c) (chartypedata[(c)>>5] |= (1UL<<((c)&31UL)))
#define clrbit_isword(c) (chartypedata[(c)>>5] &= ~(1UL<<((c)&31UL)))


When you are filling your table initially, use the setbit_isword(character) macro.

If, for whatever reason, you need to clear an entry, use the clrbit_isword(character) macro.

The point of this code is that it uses just one bit to represent the "isword" status for each character. You therefore get a table that is only 32 bytes rather than 256.

One slight difference to be wary of is that you can only depend on this version of isword() to return 0 if false and something else if true (it could be any power of 2 value from 1 to 2^31) but that wont affect your logic.

[Smack]

@Karlos

Since your 030 has only 256 bytes of data cache, you might want to redesign your character table like so:

May I express my doubts that this will make the table lookups any faster.

While the bit array needs less memory and can therefore fit into the 68030's tiny cache, the extra instructions required for the bitwise access will probably nullify the performance boost achieved by the cache hits. (I haven't counted the instruction cycles, yet)

Here's some example code in M68k assembly to support my claim:

Code: [Select]


;  input: d0 = character (values 0...255)
;  input: a0 = address of lookup table
; output: status bit Z (Zero)

; alternative (1) byte array lookup
tst.b   (a0,d0.w)       ;(cache-miss likely on 68030)

; alternative (2) bit array lookup (supposed C compiler output)
move.w  d0,d1
lsr.w   #5,d1           ;d1=table offset (long words)
move.l  (a0,d1.w*4),d1  ;d1=long word value
and.l   #31,d0          ;d0=bit number (modulo 32)
moveq   #1,d2
lsl.l   d0,d2           ;d2=bit mask
and.l   d2,d1

; alternative (3) bit arry lookup (asm optimized)
move.w  d0,d1
lsr.w   #3,d1           ;d1=table offset (bytes)
btst    d0,(a0,d1.w)    ;(implied: d0=bit number modulo 8)

Depending on the number of wait states caused by the cache-miss during byte array lookup (alternative 1), even the hand-optimised bit array lookup (alternative 3) may be slower due to the extra instructions, let alone the C version (alternative 2). If the code runs on a 68040 or 060 then things will look even worse for the bit array...

I think this kind of performance tweaking is way off-topic for a beginners session in C, anyway.

Sorry for nagging.  ;-)

[Karlos]

Smack wrote:

Depending on the number of wait states caused by the cache-miss during byte array lookup (alternative 1), even the hand-optimised bit array lookup (alternative 3) may be slower due to the extra instructions, let alone the C version (alternative 2). If the code runs on a 68040 or 060 then things will look even worse for the bit array...

It was faster than the basic char array on my 040. I reasoned that it may well be faster on the 030 but as you say, mileage varies ;-)

I think this kind of performance tweaking is way off-topic for a beginners session in C, anyway.

Absolutely :-D

[Smack]

It was faster than the basic char array on my 040. I reasoned that it may well be faster on the 030 but as you say, mileage varies ;-)

Interesting! Why's that? Can the longword memory access be that much faster than the byte memory access?

[SamuraiCrow]

Smack wrote:

It was faster than the basic char array on my 040. I reasoned that it may well be faster on the 030 but as you say, mileage varies ;-)

Interesting! Why's that? Can the longword memory access be that much faster than the byte memory access?

No...  The '040 has a 4k cache on the die instead of a 256 byte cache.

[Smack]

SamuraiCrow wrote:
No...  The '040 has a 4k cache on the die instead of a 256 byte cache.

Yeah, I know. The byte array (256 bytes) should easily fit into that larger cache, which should give the byte lookup a boost. But Karlos observed a better performance of the bit lookup with its smaller table (32 bytes) but more instructions.

Why? Cache-misses due to lookup table of 256 bytes not being in 68040 data cache? Longword lookups faster than byte lookups? Hm...

[Karlos]

I'll try a hand optimised assembler implementation of each one later.

The speed was based on testing a very large string (several MB worth) in memory. The speed increase wasn't accurately measurable when reading from a file (even with buffering) since IO overhead tends to be the limiting factor in both cases.

Perhaps you are looking at the problem in too small a scope. The source data also enters the cache. In this case, you are reading something that is effectively streaming (from memory) which will involve cache line transfers to boost the speed of successive character accesses, but fundamentally, this will pollute the cache with values from the string that are only ever used once (this is a common problem with stream style processing).
Therefore, perhaps the smaller bit-table is less affected due to the fact that it's both smaller and fact that a lot of the time the same 32-bit word will be repeatedly hit for many different characters.

Its also possible that the compiler didnt generate code for the byte table lookup that was especially optimal compared to the bit lookup.

[Smack]

Karlos wrote:
The source data also enters the cache.
...
Therefore, perhaps the smaller bit-table is less affected due to the fact that it's both smaller and fact that a lot of the time the same 32-bit word will be repeatedly hit for many different characters.

Yes, that's probably the explanation of the results.

But as you said, in the presence of file I/O it seems useless to optimise this part of the program. It's just a nice technical exercise with no practical benefit. Have fun.  ;-)

[guru-666]

wow so many ppl interested in some average chicks c homework, amazing....  You guy's know that python has this kind of function built in already.

[AmireX]

guru-666 wrote:
wow so many ppl interested in some average chicks c homework, amazing....  You guy's know that python has this kind of function built in already.

Yes python is the better choice :-), could look like this:

Code: [Select]


import sys

argc = len(sys.argv)
if argc < 2:
  print &quot;Usage: wordcount <file name>&quot;
  sys.exit(1)

word_l = open(sys.argv[0]).read().split()
len_d = {}
for word in word_l:
  size = len(word)
  if size in range(1,4): size = 3
  if size > 10:          size = 10
  if len_d.has_key(size): len_d[size] += 1
  else:                   len_d[size] = 1
print len_d


[mel_zoom]

guru-666:

"wow so many ppl interested in some average chicks c homework, amazing....  You guy's know that python has this kind of function built in already."

I guess the point that this is all about learning C and not about which language is better for the task is wasted on some average python progammers :-P

It is probably even easier in Perl or PHP.

[guru-666]

that's cool, can't realy find fault in ppl learning new things!  I just wonder why you choose C, as that a language is old and on it's way out.  I perfer object oriented stuff.  Anyway I'm not even average I'm piss poor at coding.
I'm getting to old to learn hard things with out a goal.  I use (MEL, maya's scripts language) and now python for my 3d animation needs.... to me coding is sensless unless you have a goal.  When I told the folk here at work that I was going to go back and learn C, they laughed at me and told me to just use python and move forward..... So if your looking for work...
anyway, good luck!


PERL!  that syntax sucks..... but them regular expression, wow.

[mel_zoom]

People keep saying that C (and C++) are obsolete and that some newer language does it all so much better.

What I cant understand is how people can think that when most of these languages require C in order to be compiled and maintained. How many of them can be genuinely built using only their own language?

As far as I understand Java, Perl, Python, PHP and all of the .net languages are all implemented in C at some level and cannot be built without it!

When everybody has forgotten C who will actually maintain the languages they have migrated to?

[Piru]

I just wonder why you choose C, as that a language is old and on it's way out.

How is age of the language relevant? Regardless, C is not going anywhere.

IMO C is probably the best choice for overall programming skills. When you know C, it is easy to extend your knowlege to other languages.