It’s not good. It’s a good ol-fashioned four sided one. Three of the sides I can clean fine. The fourth has very small holes for fine grating.I clean it with hot water but then there always seems to be some bits of cheese left stuck in it.Using a dishcloth or teatowel just rips it to shreds and then I get bits of cloth/towel/finger in my next cheese dish.Any ways of getting this orrid stuff out?
Any small scrub brush works great. Best to get something a lot smaller than the previous post. That way you can manuever it inside the grater & dislodge the chunks from the back side. They come out much easier that way.
I have something that looks like an overgrown toothbrush with a head about 3/4" x 2-1/2" & 3/8" stiff bristles. I use it for scrubbing potatoes, etc., and also for getting gunk out of cracks & crevices in all sorts of cooking utensils.
Those big globby brushes are for people afraid to get their hands wet or near (iick!!) food residue. The leverage is lousy & the heads are so big that they’ll only work well on a large flat surface like a dinner plate.
Another trick is to spray the grater with cooking spray before you use it. The cheese slides right off. 
I gave up on the four-sided kind and bought two flat ones, fine and coarse. I also always make sure to clean the cheese off immediately after use, before it dries, and just run them through the soapy water with the rest of the dishes later.
I use hot water and a tooth brush. It really gets into those little holes.
Bar of soap first, then…
The brush technique sounds like it may work very well; I’ll have to try that. My current method is to use soapy water to remove as much as possible, then use a scouring pad with a sponge (still in soapy water) to remove the rest. If you only scour up, in the opposite direction to the one used to grate cheese, you can remove the residue without grating the scouring pad (much). That works even on the small-holes side, but I don’t think it would work on the side with the star-shaped holes used for grating cheese into a powder. The solution is not to use that side. =) It’s mostly for hard cheese like Parmesan anyway, and the small shredding holes are just as effective for those cheeses. Or you could get a mechanical grater, which doesn’t need to be cleaned and eliminates much of your need for fine grating. Most restaurants use finely-grated Parmesan rather than powder, so there might be a reason why the small holes are better than the star-shaped holes.
I tried to find names for the sides of a cheese grater, but I failed. ‘Extra fine’, ‘fine’, ‘coarse’ and ‘julienne’ was the best I got. I did find a suggestion to rub the grater with vegetable oil or spray it with non-stick spray before using it to reduce the residue.